Back to Blog

已知二叉树后序遍历序列是DABEC 中序遍历列是 DEBAC ,它的前序遍历序列是:

function buildTree(postorder, inorder): if postorder is empty: return null

// 1. 根节点是后序序列的最后一个元素
rootVal = postorder[-1]
root = new TreeNode(rootVal)

// 2. 在中序序列中找到根节点的位置
idx = inorder.index(rootVal)

// 3. 划分左右子树
leftInorder  = inorder[0:idx]
rightInorder = inorder[idx+1:]

leftPostorder  = postorder[0:len(leftInorder)]
rightPostorder = postorder[len(leftInorder):-1]

// 4. 递归构造左右子树
root.left  = buildTree(leftPostorder,  leftInorder)
root.right = buildTree(rightPostorder, rightInorder)

return root