题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路
可以先自己尝试手画一遍，怎么根据前序和中序遍历结果画出原始的二叉树
前序遍历：根左右
中序遍历：左根右
可以知道在中序遍历中，根的位置可以分割左右子树，而前序遍历第一个节点就是根，这样可以初步分出最大的左右子树
按照这个方法，找到根的位置，继续在得到的左右子树中分割
代码
root.left = reBuild(pre, stPre + 1, i - stIn + stPre, in, stIn, i - 1)
stPre+1 ：每次查找下一个点
i - stIn + stPre ：搜题解这样写的，多画了几次发现确实是这样，但是自己不知咋推出来的，有大佬路过可以答疑解惑下 :）
root.right = reBuild(pre, i - stIn + stPre + 1, edPre, in, i + 1, edIn)
i - stIn + stPre + 1 ：左子树+1就是右子树的开始
edPre ：一直查到前序遍历的最后一个节点
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
if (pre.length == in.length && pre.length != 0) {
TreeNode root = reBuild(pre, 0, pre.length - 1, in, 0, in.length - 1);
return root;
}
return null;
}
// 分割左右子树的递归过程
// stPre：搜索前序遍历的起点 edPre：搜索前序遍历的终点
// stIn/edIn以此类推
public TreeNode reBuild(int[] pre, int stPre, int edPre, int[] in, int stIn, int edIn) {
if (stPre > edPre || stIn > edIn) return null;
// 每次都new一个新的节点
TreeNode root = new TreeNode(pre[stPre]);
// 查找根节点的for循环
for (int i = stIn; i <= edIn; i++) {
// 如果满足条件，则该点就是根节点
if (pre[stPre] == in[i]) {
// 递归左子树，分割分割再分割
root.left = reBuild(pre, stPre + 1, i - stIn + stPre, in, stIn, i - 1);
// 递归右子树，分割分割再分割
root.right = reBuild(pre, i - stIn + stPre + 1, edPre, in, i + 1, edIn);
}
}
return root;
}
Refer
Log
- 20190828 xiaomi init