Medium
首先,要理解中序与后序的遍历区别:
中序:前-中-后
后序:前-后-中
构造一棵树的话,我们必须要确定根节点,然后确定左子树的元素和右子树的元素。同理,子问题也是这样,递归求解。
以上,尝试写一下代码,AC!
python3
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
def helper(cur, start, end):
if start >= end:
return None
node = TreeNode()
for p in range(cur - 1, -1 , -1):
if postorder[p] in inorder[start:end]:
i = inorder.index(postorder[p])
node.val = postorder[p]
break
node.left = helper(cur - 1, start, i)
node.right = helper(cur - 1, i+1, end)
return node
return helper(len(postorder), 0, len(postorder))