重建二叉树

在线测评地址:牛客网

题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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
}
// 测试
/* var pre = [1,2,4,7,3,5,6,8]
var vin = [4,7,2,1,5,3,8,6]
reConstructBinaryTree(pre, vin) */