[Tree]105. Construct Binary Tree from Preorder and Inorder Traversal

• 分类：Tree
• 时间复杂度: O(n) 这种把树的节点都遍历一遍的情况时间复杂度为O(n)
• 空间复杂度: O(h) 树的节点的深度

105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: 'List[int]', inorder: 'List[int]') -> 'TreeNode':
        
        if preorder==None or inorder==None or len(preorder)!=len(inorder):
            return None
        return self.helper(preorder,inorder,0,0,len(inorder)-1)
    
    def helper(self,preorder,inorder,pre_st,in_st,in_ed):
        if pre_st>=len(preorder) or in_st>in_ed:
            return
        root=TreeNode(preorder[pre_st])
        for i in range(in_st,in_ed+1):
            if inorder[i]==preorder[pre_st]:
                break
        root.left=self.helper(preorder,inorder,pre_st+1,in_st,i-1)
        root.right=self.helper(preorder,inorder,pre_st+(i-in_st)+1,i+1,in_ed)
        return root

讨论：

1.考察前序遍历和中序遍历的特点，利用递归/分治来解这道题
2.注意几个位置，一个pre_st，一个in_st,in_ed