题目:[1]
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如,给出:
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
思路
参数:
思路
查找根节点,及当前根节点左右子节点的逻辑:
递归参数:
终止条件:
因为后续遍历是先遍历左子树再遍历右子树最后遍历根节点, 那么右子树的索引一定大于左子树的索引,当不满足是说明节点遍历完成,终止递归
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} inorder 中序遍历
* @param {number[]} postorder 后序遍历
* @return {TreeNode}
*/
var buildTree = function(inorder, postorder) {
let rootIndex = postorder.length - 1,
map = new Map()
// 记录在中序遍历数组中每个节点的位置,方便在得到根节点时查找左右子树节点
for (let i = 0; i < inorder.length; i++) {
map.set(inorder[i], i)
}
function dfs(leftIndex, rightIndex) {
if (leftIndex > rightIndex) return null
let root = new TreeNode(postorder[rootIndex]),
i = map.get(postorder[rootIndex])
rootIndex--
root.right = dfs(i + 1, rightIndex)
root.left = dfs(leftIndex, i - 1)
return root
}
return dfs(0, inorder.length - 1)
}
倒序遍历中序遍历数组(inorder):
倒序遍历后序遍历数组(postorder):
那么,倒序遍历后序遍历数组数组时,两个相邻的节点[a,b],两个节点在二叉树中的关系:
实现
var buildTree = function(inorder, postorder) {
let rootIndex = postorder.length - 1,
root = new TreeNode(postorder[rootIndex]),
// 维护下一次遍历追击子树的最新子树
queue = [root],
inorderIndex = inorder.length - 1
rootIndex--
while (rootIndex >= 0) {
let node = queue[queue.length - 1],
nodeVal = postorder[rootIndex]
// 不等于上一个生成子树的节点,则说明是上一个子树的右节点
if (node.val !== inorder[inorderIndex]) {
node.right = new TreeNode(nodeVal)
queue.push(node.right)
} else {
// 维护inorder的倒序遍历索引跳过已经生成树的根节点
while (
queue.length &&
queue[queue.length - 1].val === inorder[inorderIndex]
) {
node = queue.pop()
inorderIndex--
}
// 情况 2
node.left = new TreeNode(nodeVal)
queue.push(node.left)
}
rootIndex--
}
return root
}