已知二叉树后序遍历序列是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