Construct Tree

Question

Construct tree from inorder, preorder, postorder

preorder and inorder postorder and inorder

思路

For example:

                1
        --------|-------
        2               3
    ----|----       ----|----
    4       5       6       7

• 前序遍历 1245367
• 中序遍历 4251637
• 后续遍历 4526731

仍然以上面那棵二叉树为例，我们可以发现，对于后序遍历来说，最后一个元素一定是根节点，也就是1。然后我们在中序遍历的结果里面找到1所在的位置，那么它的左半部分就是其左子树，有半部分就是其右子树。

Solution

preorder and inorder

class Solution:
    """
    @param preorder : A list of integers that preorder traversal of a tree
    @param inorder : A list of integers that inorder traversal of a tree
    @return : Root of a tree
    """                                                                                                                                   
    def buildTree(self, preorder, inorder):
        # write your code here
        if not preorder or not inorder:
            return None
        root = TreeNode(preorder[0])
        index = self.findIndex(inorder, root.val)
        root.left = self.buildTree(preorder[1: index + 1], inorder[:index])
        root.right = self.buildTree(preorder[index + 1:], inorder[index + 1:])
        return root

    def findIndex(self, inorder, value):
        for i, val in enumerate(inorder):
            if val == value:
                return i

postorder and inorder

class Solution:
    """
    @param preorder : A list of integers that preorder traversal of a tree
    @param inorder : A list of integers that inorder traversal of a tree
    @return : Root of a tree
    """
    def buildTree(self, inorder, postorder):
        # write your code here
        if not postorder or not inorder:
            return None
        root = TreeNode(postorder[-1])
        index = self.findIndex(inorder, root.val)
        root.left = self.buildTree(inorder[:index], postorder[:index])
        root.right = self.buildTree(inorder[index + 1:], postorder[index:len(postorder)-1])
        return root

    def findIndex(self, inorder, value):
        for i, val in enumerate(inorder):
            if val == value:
                return i

enumerate(list) to get index