-
题目
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
-
解题
-
树的遍历
与线性结构（如数组 链表 队列）不同，树有多种遍历的方式。常见的有三种：
源于维基百科
(a)中序遍历（左，中，右）：2 7 5 6 11 2 5 4 9
(b)前序遍历（中，左，右）：2 7 2 6 5 11 5 9 4
(c)后序遍历（左，右，中）：2 5 11 6 7 4 9 5 2
以中遍历为例：
1.遍历左子树 inOrder(left-subtree)
2.访问父节点
3.遍历右子树 inOrder(right-subtree)
var output;
function inOrder(root){
if root{
inOrder(root.left);
output = output + string(root.val);
inOrder(root.right);
}
}
中序遍历可以用于通过二分查找树(BST)构造一个非降序的序列，后序遍历可用于删除树
-
通过中序 + 前序/后序 构建一颗二叉树
- 从前序中取一个值，并将preIndex + 1
- 以该值构建一个节点tNode
- 找到该值在中序中的index，记为inIndex
- 回溯法调用buildTree函数，将inIndex之前的标记为左子树，之后的标记为右子树
var preIndex = 0;
function buildTreeHelper(pre,vin,strt,end){
if (strt > end){
return null;
}
const tNode = new TreeNode(pre[preIndex]);
preIndex += 1;
if (strt === end){
return tNode;
}
const inIndex = vin.findIndex(x => x === tNode.val);
tNode.left = buildTreeHelper(pre,vin,strt,inIndex - 1);
tNode.right = buildTreeHelper(pre,vin,inIndex + 1,end);
return tNode;
}
