105. Construct Binary Tree from Preorder and Inorder Traversal

问题描述

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

思路

• 用recursive的方法，从上往下append child nodes，分左右recur；
• 通过对比preorder和inorder，得出每个 子root 和他的左右两棵树；
  每次return head（即 子root，新建的Node）

当到达leaf时，leaf也是子root，只不过此时preorder的长度不符合recur条件，直接return None，形成base case

    def buildTree(self,preorder, inorder):
        """
        :param preorder: List[int]
        :param inorder: List[int]
        :return: TreeNode
        """

        if not preorder or not inorder:
            return

        head = None
        if len(preorder) > 0:
            index = inorder.index(preorder[0])
            head = TreeNode(preorder[0])
            head.left = self.buildTree(preorder[1:index+1], inorder[:index])
            head.right = self.buildTree(preorder[index+1:], inorder[index+1:])
        return head

转载于:https://www.jianshu.com/p/15072c5028c6