题解 | #重建二叉树#

Divider and conquer with recursion:
for each tree, it is composed of three parts: root-left branch, right branch. each branch is also composed of root>left>right. so we could extend the root recursively by concatenating
its left and right node:

class Solution:
    # return the root of TreeNode
    def reConstructBinaryTree(self, pre, vin):
             # write code here
        if not pre or not vin:
            return None 
        self.hash_={}

        for i in range(len(vin)):
            self.hash_[vin[i]]=i
        root = TreeNode(pre[0])     
        # index is used in inorder list to slice the left and right brach based on current 
        # root or subroot; length_left is the length of left branch nodes, it is used in 
        # preorder list to slice the left and right branch based on the frist node of 
        # of updated preorder list is the current root (root or subroot)
        index=self.hash_[pre[0]]
        length_left = len(vin[:index])

        if index == 0:
            root.left = None
        else:
            root.left = self.reConstructBinaryTree(pre[1:length_left+1], vin[:index])
        if length_left + 1 < len(pre):
            root.right = self.reConstructBinaryTree(pre[length_left+1:], vin[index+1:])
        else:
            root.right = None
        return root