-
Notifications
You must be signed in to change notification settings - Fork 0
/
7.js
29 lines (28 loc) · 1.16 KB
/
7.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假
* 设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
* 思路:前序遍历的第一个值必然是根结点,而在中序中对应元素的左边就是根结点左子树的全部节点,右边则是右子树的全部内地哪(同时也可以统计出左右子树的节点数,设为 m,n)
* 而前序遍历的第 1-m+1 个字符则自然是左子树的节点,因此可以用递归来处理
*/
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function reConstructBinaryTree(pre, vin) {
if (!pre || !vin || pre.length !== vin.length || pre.length === 0) {
return null;
}
const val = pre[0];
const node = new TreeNode(val);
const count = vin.indexOf(val);
node.left = reConstructBinaryTree(
pre.slice(1, count + 1),
vin.slice(0, count)
);
node.right = reConstructBinaryTree(
pre.slice(count + 1),
vin.slice(count + 1)
);
return node;
}