105. Construct Binary Tree from Preorder and Inorder Traversal

Loading...LeetCode

理解inordertraversal list的一个性质：

当前node左子树的元素一定在它的左边，右子树的元素一定在它右边

遍历preorder中的元素：

1. 针对每个元素node，都在inorder中找下位置idx

2. 然后idx左边就是node left subtree 的 inorder，右边就是right subtree 的inorder

递归完成这个遍历，过程中 preorder的首个元素会被不断地 pop 出来。

01/17/2021 Update:

1. preorder 先序遍历的第一个节点即为根节点。

2. 以根节点来裁切 inorder，会发现两边的 subarray 分别是根节点左右子树的 inorder。

第二点其实要依靠题目里这个提示才能得出：

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

递归直到 inorder 中没元素了（即当前节点不再有children）结束。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder: return None
        
        # 把第一个元素pop出来
        rootVal = preorder.pop(0)
        root = TreeNode(rootVal)
        idx = inorder.index(rootVal)
        
        # 这个写法需要做切片，有点慢，其实可以传递index规避切片，不过这样也能submit，就不改了
        root.left = self.buildTree(preorder, inorder[:idx])
        root.right = self.buildTree(preorder, inorder[idx+1:])

        return root