题目描述

样例

输入：inorder = [9,3,15,20,7]
    postorder = [9,15,7,20,3]
输出:
    3
   / \
  9  20
    /  \
   15   7

算法1

(递归) $O(n)$时间 和$O(n)$空间

Py 代码

class Solution:
    def buildTree(self, inorder, postorder):
        map_inorder = {}
        for i, val in enumerate(inorder): map_inorder[val] = i
        def recur(low, high):
            if low > high: return None
            x = TreeNode(postorder.pop())
            mid = map_inorder[x.val]
            x.right = recur(mid+1, high)
            x.left = recur(low, mid-1)
            return x
        return recur(0, len(inorder)-1)

算法2 #105题 一样的思路

(递归Recursion) $O(n)$

iterator and map

时间复杂度

Py 代码

def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        inor_dict = {}
        for i, num in enumerate(inorder):
            inor_dict[num] = i
        pre_iter = iter(preorder)

        def helper(start, end):
            if start > end:return None
            root_val = next(pre_iter)
            root = TreeNode(root_val)
            idx = inor_dict[root_val]
            root.left = helper(start, idx-1)
            root.right = helper(idx+1, end)
            return root

        return helper(0, len(inorder) - 1)