106. Construct Binary Tree from Inorder and Postorder Traversal

Loading...LeetCode

思路见Q105：

105. Construct Binary Tree from Preorder and Inorder Traversal

这题的主要变化是：

1. 需要逆序遍历postorder（其实逆序postorder就是先搜right subtree的preorder）

2. 相应地，要先确定 rght subtree 再去确定 left

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder or not postorder: return None
        rootVal = postorder.pop()
        root = TreeNode(rootVal)
        idx = inorder.index(rootVal)
        
        root.right = self.buildTree(inorder[idx+1:], postorder)
        root.left = self.buildTree(inorder[:idx], postorder)
        
        return root