重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
时间限制：1秒 空间限制：32768K
思路
递归思想，每次可以依据前序遍历的第一个元素，确定左子树和右子树。
代码
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
return reConstruct(0, pre.length - 1, 0, vin.length, pre, vin);
// write code here
function reConstruct(preStart, preTreeEnd, inStart, inEnd, preOrder, vinOrder) {
if(preStart > preTreeEnd || inStart > inEnd) {
return null;
}
var root = new TreeNode(preOrder[preStart]);
for(var i = inStart; i <= inEnd; i++) {
if(vinOrder[i] == preOrder[preStart]) {
root.left = arguments.callee(preStart + 1, preStart + i - inStart,
inStart, i - 1, preOrder, vinOrder);
root.right = arguments.callee(preStart + 1 + i - inStart, preTreeEnd,
i + 1, inEnd, preOrder, vinOrder);
break;
}
}
return root;
}
}
运行时间：39ms
占用内存： 7104k
问题
- 二叉树的遍历详解（前序中序后序层次-递归和非递归）：https://blog.csdn.net/gatieme/article/details/51163010
- 根据前序遍历和中序遍历，后序遍历和中序遍历重构二叉树：https://blog.csdn.net/ahaha413525642/article/details/78210024
