leetcode105:从前序与中序遍历序列构造二叉树
sisterAn opened this issue · 5 comments
sisterAn commented
输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
限制:
0 <= 节点个数 <= 5000
附赠leetcode地址:leetcode
sisterAn commented
解法:递归法
前序遍历:根左右
中序遍历:左根右
我们通过前序遍历可以知道二叉树的根
知道二叉树的根,根据中序遍历,我们可以知道根的左右子树的中序遍历及左右子树节点数目
知道左右子树的节点数目,结合前序遍历,我们就知道左右子树的前序遍历
var buildTree = function(preorder, inorder) {
if(!preorder.length) return null
const node = new TreeNode(preorder[0])
const index = inorder.indexOf(preorder[0])
const inLeft = inorder.slice(0, index)
const inRight = inorder.slice(index + 1)
const preLeft = preorder.slice(1, index + 1)
const preRight = preorder.slice(index + 1)
node.left = buildTree(preLeft, inLeft)
node.right = buildTree(preRight, inRight)
return node
};
luweiCN commented
仔细分析前序遍历和中序遍历可以知道(以题目为例):
- 前序遍历的第一个元素一定是根节点,这里是
3
- 找到根节点之后,根节点在中序遍历中把数组一分为二,即两个数组
[9]
和[15, 20, 7]
,这两个数组分别是根节点3
的左子树和右子树的中序遍历。 - 前序遍历数组去掉根节点之后是
[9,20,15,7]
,而这个数组的第1项[9]
(左子树的大小)和后3项[20, 15, 7]
(右子树的大小)又分别是左子树和右子树的前序遍历
到这里已经很明显了,用递归
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var buildTree = function (preorder, inorder) {
if (preorder.length) {
let head = new TreeNode(preorder.shift());
let index = inorder.indexOf(head.val);
head.left = buildTree(
preorder.slice(0, index),
inorder.slice(0, index)
);
head.right = buildTree(preorder.slice(index), inorder.slice(index + 1));
// 这里要注意,preorder前面shift一次长度比inorder小1
return head;
} else {
return null;
}
};
plane-hjh commented
解法:二叉树的前序遍历和中序遍历
二叉树的前序遍历中,第一个数字是二叉树的根节点。在中序遍历中,根节点位于序列的中间,即根节点的左边是左子树节点的值,右边是右子树节点的值。
由前序遍历 [3,9,20,15,7]
可知,3
是根节点。中序遍历 [9,3,15,20,7]
可知,根节点 3
的左边是左子树节点 9
,右边是右子树节点 15
,20
,7
。所以
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
var buildTree = function(preorder, inorder) {
if(!preorder.length || !inorder.length) {
return null
}
const rootVal = preorder[0]
const node = new TreeNode(rootVal)
// i有两个含义,一个是根节点在中序遍历结果中的下标, 另一个是当前左子树的节点个数
let i = 0;
for(; i < inorder.length; ++i) {
if(inorder[i] === rootVal) {
break;
}
}
// i主要是求出根节点在中序遍历序列中的位置。那么i位置前面的都是左子树的值,后边的都是右子树的值。
// 中序遍历和前序遍历的左子树和右子树节点的个数都分别相等
// preorder.slice(1, i+1) 在前序遍历里面,左节点有多少个
// inorder.slice(0, i) 在中序遍历里面,左节点就是根节点位置i前面的那些
node.left = buildTree(preorder.slice(1, i+1), inorder.slice(0, i))
node.right = buildTree(preorder.slice(i+1), inorder.slice(i + 1))
return node
};
AnranS commented
var buildTree = (preorder, inorder) => {
let map = new Map()
for (let i = 0; i < inorder.length; i++) {
map.set(inorder[i], i)
}
return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map)
}
function helper(preorder, p_start, p_end, inorder, i_start, i_end, map) {
if (p_start > p_end) return null // preorder为空
let rootVal = preorder[p_start] // 根节点的值
let root = new TreeNode(rootVal) // 根节点
let mid = map.get(rootVal) // 根节点在inorder的位置
let leftNum = mid - i_start // 左子树的节点数
root.left = helper(preorder, p_start + 1, p_start + leftNum, inorder, i_start, mid - 1, map)
root.right = helper(preorder, p_start + leftNum + 1, p_end, inorder, mid + 1, i_end, map)
return root
}
Forever17s commented
var buildTree = function(preorder, inorder) {
if (preorder.length === 0) return null; // 在数组长度为0时结束递归
const root = new TreeNode(preorder[0]); // 前序遍历第一个元素为根节点
const mid = inorder.indexOf(preorder[0]); // 获取根节点中序遍历中的索引
// 根据索引来切割数组 对子数数组继续递归
root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
return root;
};
相似题型
leetcode106. 从中序与后序遍历序列构造二叉树
var buildTree = function(inorder, postorder) {
if(!inorder.length) return null // 在数组长度为0时结束递归
const n = postorder.length
const root = new TreeNode(postorder[n-1]) // 中序遍历最后一个元素为根节点
const mid = inorder.indexOf(postorder[n-1]) // 获取根节点后序遍历中的索引
// 根据索引来切割数组 对子数数组继续递归
root.left = buildTree(inorder.slice(0,mid),postorder.slice(0,mid))
root.right = buildTree(inorder.slice(mid + 1),postorder.slice(mid,n-1))
return root
};