4.17重建二叉树 - WisperDin/blog GitHub Wiki
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路:
递归实现,从根结点开始,逐步构建左右分支,直至构建出整个树
PreIndex :: 0,1,2,3,4,5,6,7
Pre :: 1,2,4,7,3,5,6,8 (L:1~3 R:4~7)
Pre :: 1,[2,4,7],[3,5,6,8] (L:1~3 R:4~7)
InIndex :: 0,1,2,3,4,5,6,7
In :: 4,7,2,1,5,3,8,6 (L:0~2 R:4~7)
In :: [4,7,2],1,[5,3,8,6] (L:0~2 R:4~7)
回忆用手用笔做的过程:
-
从前序表达式中找第一个元素,知道为根节点
-
在中序表达式中搜索这个根节点所在位置, 中序表达式中 根节点往左为左子树,根节点往右为右子树,同样,在 前序表达式 中 划分左子树和右子树 的对应位置
-
对左子树的前序与中序式子,右子树的前序与中序式子,递归进行1,2步骤
其中
转化为编程实现
-
步骤1没啥问题,就拿前序表达式中第一个元素作为根节点,步骤二在中序表达式中搜索这个根节点位置也不难,就是一个遍历搜索
-
然后,划分中序的左子树与右子树也不难,左子树::(开始
根结点位置-1) 右子树::(根节点位置+1结束) -
难点 是要在前序中确定左右子树的划分, 以前手做的时候的确可以一眼看出前序中的左子树,但是到计算机实现的时候就有点迷糊了,, 于是细化 这个步骤:
- 首先分析左子树,由于前序的顺序是 中左右 ,所以左子树的开始位置肯定在 根节点的向后一个位置,
- 左子树结束位置的判定,来源于从中序得来的左子树元素个数,然后进行偏移得到左子树结束位置
- 前序左子树 表达式 (根节点位置+1~根节点位置+左子树元素个数)
- 接着分析右子树,右子树的开始位置,是从左前序开始位置偏移左子树元素个数得到
- 右子树的结束位置就是前序末尾
- 前序右子树 表达式 (左前序位置偏移左子树元素个数~末尾)
实现(某位大佬的代码,看了好久之后理解了,加了注释,中间变量)
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
return root;
}
//前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
private TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
if (startPre>endPre || startIn>endIn)
return null;
TreeNode root = new TreeNode(pre[startPre]);
for (int i = startIn; i <= endIn; i++)
if (in[i] == pre[startPre]) {
// i-startIn 表示通过中序根节点位置 往左 得知的的 !!左子树元素个数
//left----------
int leftPreStart = startPre + 1;//开始位置=前序根节点位置+1
int leftPreEnd = startPre + i - startIn; //末尾位置=(开始位置-1)+左子树元素个数
//
int leftInStart = startIn;//左子树的中序开始位置
int leftInEnd = i - 1; //左子树的中序结束位置 中序中根节点位置的前一个
//right----------
int rightPreStart = i - startIn + startPre + 1;//右前序开始位置=从左前序开始位置 偏移 左子树元素个数
int rightPreEnd = endPre;//前序末尾
//
int rightInStart = i + 1 ; // 右子树的中序开始位置
int rightInEnd = endIn; //中序末尾
root.left = reConstructBinaryTree(pre, leftPreStart, leftPreEnd, in, leftInStart, leftInEnd);
root.right = reConstructBinaryTree(pre, rightPreStart, rightPreEnd, in, rightInStart, rightInEnd);
break;
}
return root;
}
}