在线测评地址：牛客网
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路
前序遍历： 根左右
中序遍历： 左根右
前序遍历中第一个数为树的根节点，在中序遍历中找到根，根的左边属于根的左子树，根的右边属于根的右子树。
将左子树、右子树看成新的树，在前序遍历中第一个数同样为此树的根节点，重新寻找其左子树和右子树，一直递归寻找
编程
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
| function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
}
function reConstructBinaryTree(pre, vin, node)
{
var Node = node || new TreeNode(pre[0])
var index = vin.indexOf(pre[0])
var preLeft = pre.slice(1, index + 1)
var vinLeft = vin.slice(0, index)
var preRight = pre.slice(index + 1, pre.length)
var vinRight = vin.slice(index + 1, vin.length)
if (preLeft.length > 0) {
Node.left = new TreeNode(preLeft[0])
reConstructBinaryTree(preLeft, vinLeft, Node.left)
}
if (preRight.length > 0) {
Node.right = new TreeNode(preRight[0])
reConstructBinaryTree(preRight, vinRight, Node.right)
}
return Node
}
|