每日一道算法题04:重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
限制：
0 <= 节点个数 <= 5000
解题方案
前序遍历性质：节点按照 [根节点 | 左子树 | 右子树 ] 排序。
中序遍历性质：节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。
以题目示例为例：
前序遍历划分 [3 | 9 | 20 15 7 ]
中序遍历划分 [ 9 | 3 | 15 20 7 ]
根据以上性质，可得出以下推论：
-
前序遍历的首元素 为 树的根节点 node 的值。 -
在中序遍历中搜索根节点 node 的索引 ，可将 中序遍历 划分为 [ 左子树 | 根节点 | 右子树 ]。 -
根据中序遍历中的左 / 右子树的节点数量，可将 前序遍历 划分为 [ 根节点 | 左子树 | 右子树 ]。
如何找到第一个根节点？
为什么要是第一个根节点呢？因为你是从第一个开始根开始创建的呀。
前序遍历：根节点 -- 左节点 -- 右节点
中序遍历：左节点 -- 根节点 -- 右节点
第一个根节点必然出现在前序遍历的第一个位置！但是对于中序遍历来说，我们不知道第一个根前面左子树的长度，所以无法得知！因此最简单的切入点就是通过前序遍历找到第一个根节点
如何找到第一个左节点？
这个在前序遍历中也很好看出来，第一个左节点就在第一个根节点的右边1个单位，即：pre_root_index + 1
如何找到第一个右节点？
我们找到了第一个根，第一个左节点，那如何确定第一个右节点呢？
对于前序遍历而言，我们已经知道了根、左节点，那么很显然，右节点的下标 = 根节点下标 + 左子树的长度 + 1（在前序遍历数组中），现在唯一不确定的就是左子树的长度，这一点可以很简单的从中序遍历中获得，也就是左子树长度 = 根节点下标 - 左子树的左边界 （在中序遍历数组中）
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {
let map = new Map();
for (let i = 0; i< preorder.length; i++) {
map.set(inorder[i], i) // 先把中序遍历保存到map中
}
return recursive(0, 0, inorder.length - 1);
/**
* @param pre_root_idx 先序遍历的索引
* @param in_left_idx 中序遍历的索引
* @param in_right_idx 中序遍历的索引
*/
function recursive(pre_root_idx, in_left_idx, in_right_idx) {
//相等就是自己，左子树的index不可能大于右子树的
if (in_left_idx > in_right_idx) {
return null;
}
//root_idx是在先序里面的
let root = new TreeNode(preorder[pre_root_idx]);
// 有了先序的,再根据先序的，在中序中获 当前根的索引
let idx = map.get(preorder[pre_root_idx]);
// 左子树的根节点:左子树的(前序遍历）第一个，就是+1,
// 左边边界就是left，
// 右边边界是中间区分的idx-1
root.left = recursive(pre_root_idx + 1, in_left_idx, idx - 1);
// 由根节点在中序遍历的idx 区分成2段,idx 就是根
// 右子树的根index = 当前节点根index + 左子树的长度
// pre_root_idx 当前的根
// 左子树的长度 = 左子树的长度 = 左子树的左边-右边 (idx-1 - in_left_idx +1)。最后+1就是右子树的根了
root.right = recursive(pre_root_idx + (idx-1 - in_left_idx +1) + 1, idx + 1, in_right_idx);
return root;
}
};