本文共 767 字,大约阅读时间需要 2 分钟。
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.For example, given
inorder = [9,3,15,20,7]postorder = [9,15,7,20,3]
Return the following binary tree:
3 / \ 9 20 / \ 15 7
根据中序遍历和后序遍历生成二叉树。
用递归方法很容易完成,先利用后序遍历找到根节点,然后再根据中序遍历分根节点的左子树和右子树。
需要注意的是和前序+中序有所不同,后序+中序要先写root.right,而前者要先写root.left。
class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode: if inorder: node = postorder.pop() index = inorder.index(node) root = TreeNode(node) root.right = self.buildTree(inorder[index+1:], postorder) root.left = self.buildTree(inorder[:index], postorder) return root
转载地址:http://adrbb.baihongyu.com/