面试题 6: 重建二叉树
题目描述:
输入某二叉树的前序遍历和中序遍历的结果, 请重建出该二叉树. 假设输入的前序遍历和中序遍历的结果中都不含重复的数字. 例如输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列{4,7,2,1,5,3,8,6}, 则重建出图 2.6 所示的二叉树并输出它的头结点. 二叉树结点的定义如下:
- class Node{
- int e;
- Node left;
- Node right;
- Node(int x) { e = x; }
- }
这道题主要测试你对二叉树性质的了解, 非常有代表性, 不过在这之前, 我们先把二叉树的基本性质捋一遍.
二叉树的基本性质
(1)关于树
树是一种数据结构, 它是由 n(n>=1)个有限结点组成一个具有层次关系的集合.
树的基本术语有:
每个结点有零个或多个子结点
没有父节点的结点称为根节点
每一个非根结点有且只有一个父节点
除了根结点外, 每个子结点可以分为多个不相交的子树.
若一个结点有子树, 那么该结点称为子树根的 "双亲", 子树的根称为该结点的 "孩子". 有相同双亲的结点互为 "兄弟".
一个结点的所有子树上的任何结点都是该结点的后裔. 从根结点到某个结点的路径上的所有结点都是该结点的祖先.
结点的度: 结点拥有的子树的数目
叶子结点: 度为 0 的结点
分支结点: 度不为 0 的结点
树的度: 树中结点的最大的度
层次: 根结点的层次为 1, 其余结点的层次等于该结点的双亲结点的层次加 1
树的高度: 树中结点的最大层次
森林: 0 个或多个不相交的树组成. 对森林加上一个根, 森林即成为树; 删去根, 树即成为森林.
"树" 是计算机科学中非常重要的一部分内容, 它的变形和应用非常之多. 比如说, 在做通讯录的时候, Android 工程师往往喜欢用字典树来存取数据, 对于 Java 后端, 有的时候我们处理的数据的时候也需要进行区间的查询, 比如说去年你的博客在什么时间段关注你的人增长最快啊, 一天中自己的博文阅读量最高的时间段啊, 可以采用线段树来实现. 在 JDK1.8 的 HashMap 的结构中, 当元素超过 8 个的时候, 会转为红黑树等等.
不过对于 Java 开发而言, 二叉树是基础也是接触较多的一种结构.
(2)关于二叉树
二叉树是每个结点最多有两个子树的树结构. 它有五种基本形态:
1)空树;
2)只有根的树, 即单结点;
3)有根且有一个左子树;
4)有根且有一个右子树;
5)有根且有一个左子树, 有一个右子树.
二叉树的性质有:
二叉树第 i 层上的结点数目最多为 2i-1(i>=1)
深度为 k 的二叉树至多有 2k-1 个结点(k>=1)
包含 n 个结点的二叉树的高度至少为(log2n)+1
在任意一棵二叉树中, 若叶子结点的个数为 n0, 度为 2 的结点数为 n2, 则 n0=n2+1
第四条的证明: 因为二叉树中所有结点的度数均不大于 2, 设 n0 表示度为 0 的结点个数, n1 表示度为 1 的结点个数, n2 表示度为 2 的结点个数.
三类结点加起来为总结点个数, 于是便可得到: n=n0+n1+n2 (公式 1)
由度之间的关系可得第二个等式: n=n0*0+n1*1+n2*2+1 即 n=n1+2n2+1 (公式 2)
将 (公式 1)(公式 2) 组合在一起可得到 n0=n2+1
了解这第四条性质就差不多了. 如果想进一步学习二叉树的性质, 不妨去找本《离散数学》?
对二叉树遍历的理解
以这棵树为例:
前序遍历: 根结点 -> 左子树 -> 右子树(先遍历根节点, 然后左右)
- // 前序遍历以 node 为根
- public void preOrder(Node node) {
- // 终止条件
- if(node == null) {
- return;
- }
- System.out.println(node.e);
- preOrder(node.left);
- preOrder(node.right);
- }
这棵树的前序遍历为: FCADBEHGM
中序遍历: 左子树 -> 根结点 -> 右子树(在中间遍历根节点)
- // 中序以 node 为根的
- public void inOrder(Node node) {
- // 终止条件
- if(node == null) {
- return;
- }
- inOrder(node.left);
- System.out.println(node.e);
- inOrder(node.right);
- }
这棵树的中序遍历为: ACBDFHEMG
后序遍历: 左子树 -> 右子树 -> 根结点(最后遍历根节点)
- // 中序以 node 为根
- public void postOrder(Node node) {
- // 终止条件
- if(node == null) {
- return;
- }
- postOrder(node.left);
- postOrder(node.right);
- System.out.println(node.e);
- }
这棵树的后序遍历为: ABDCHMGEF
层序遍历:
- // 层序遍历
- public void levelOrder() {
- Queue<Node> q = new LinkedList<>();
- q.add(root);
- while( !q.isEmpty() ) {
- Node cur = q.remove();
- System.out.println(cur.e);
- if(cur.left != null)
- q.add(cur.left);
- if(cur.right != null)
- q.add(cur.right); // 后出
- }
- }
这棵树层序遍历为: FCEADHGBM
所谓的前序, 中序, 后序, 就是对根节点而言的, 左右的遍历顺序不变, 前序就是根节点最先遍历, 然后左右; 中序就是把根节点放在中间遍历; 后序则是把根节点放在最后遍历.
中序遍历能够帮助我们很好地确定根节点的位置, 这个就有点可怕了, 实际面试的时候, 不单单会有给出前序遍历和中序遍历的结果让你重建二叉树, 还有给出后序遍历和中序遍历结果或者 层序遍历和中序遍历的结果重建二叉树,
其他的遍历组合均不能还原出二叉树的形状, 因为无法确认其左右孩子. 例如, 前序为 AB, 后序为 AB, 则无法确认出, B 节点是 A 节点的左孩子还是右孩子, 因此无法还原.
题解
思路: 通过前序遍历获得根节点的位置, 利用根节点将中序序列分为左子树和右子树, 然后不断的递归划分即可.
代码中有解释.
- private Node buildTree(int[] pre, int preBegin, int preEnd, int[] mid, int midBegin, int midEnd) {
- // 前序遍历确第一个元素为根节点
- Node root = new Node(pre[preBegin]);
- // 用于标记中序遍历结果中根节点的位置
- int midRootLocation= 0;
- for (int i = midBegin; i <= midEnd; i++) {
- if (mid[i] == pre[preBegin]) {
- midRootLocation= i;
- break;
- }
- }
- if ( midRootLocation - midBegin>= 1 ) {
- // 递归得到左子树
- // 中序遍历: 左子树 -> 根结点 -> 右子树(在中间遍历根节点)
- // midRootLocation 标记了中序遍历结果中根节点的位置, 这个位置两端对应根节点左子树和右子树
- // midRootLocation- midBegin 表示该根节点左边的节点的数量
- // 前序遍历: 根结点 -> 左子树 -> 右子树(先遍历根节点, 然后左右)
- // preBegin 标记了前序遍历结果中根节点的位置
- // preBegin + 1 表示该根节点左子树起始位置
- // preBegin + (midRootLocation- midBegin) 表示给根节点左子树结束的位置
- Node left = buildTree(pre, preBegin + 1, preBegin + (midRootLocation- midBegin),
- mid, midBegin, midRootLocation - 1);
- root.left = left;
- }
- if ( midEnd - midRootLocation>= 1 ) {
- // 递归得到右子树
- // 原理和上面相同
- Node right = buildTree(pre, preEnd - (midEnd - midRootLocation) + 1, preEnd,
- mid, midRootLocation+ 1, midEnd);
- root.right = right;
- }
- return root;
- }
举一反三
(1)给出后序遍历和中序遍历的结果重建二叉树
思路: 通过后序获取根节点的位置, 然后在中序中划分左子树和右子树, 然后递归划分即可.
形式与上面 给出 前序遍历和中序遍历的结果重建二叉树相同
- private Node buildTree(int[] mid, int midBegin, int midEnd, int[] end, int endBegin, int endEnd) {
- Node root = new Node(end[endEnd]);
- int midRootLocation = 0;
- for (int i = midEnd; i>= midBegin; i--) {
- if (mid[i] == end[endEnd]) {
- midRootLocation = i;
- break;
- }
- }
- // 还原左子树
- if (midRootLocation - midBegin>= 1 ) {
- Node left = buildTree(mid, midBegin, midRootLocation - 1, end, endBegin, endBegin + (midRootLocation - midBegin) - 1);
- root.left = left;
- }
- // 还原右子树
- if (midEnd - midRootLocation>= 1 ) {
- Node right = buildTree(mid, midRootLocation + 1, midEnd, end, endEnd - (midEnd - midRootLocation), endEnd - 1);
- root.right = right;
- }
- return root;
- }
(2)给出层序遍历和中序遍历结果重建二叉树
思路:
(1)根据层序遍历获取根节点的位置
(2)根据 (1) 将中序划分为左子树和右子树
(3)根据 (2) 划分出的左子树和右子树分别在层序遍历中获取其对应的层序顺序
(4)然后递归调用划分.
- private Node buildTree(int[] mid, int[] level, int midBegin, int midEnd) {
- // 层序遍历的第一个结果是 根节点
- Node root = new Node(level[0]);
- // 用于标记中序遍历的根节点
- int midLocation = -1;
- for (int i = midBegin; i <= midEnd; i++) {
- if (mid[i] == level[0]) {
- midLocation = i;
- break;
- }
- }
- if (level.length>= 2) {
- if (isLeft(mid, level[0], level[1])) {
- Node left = buildTree(mid, getLevelArray(mid, midBegin, midLocation - 1, level), midBegin, midLocation - 1);
- root.left = left;
- if (level.length>= 3 && !isLeft(mid, level[0], level[2])) {
- Node right = buildTree(mid, getLevelArray(mid, midLocation + 1, midEnd, level), midLocation + 1, midEnd);
- root.right = right;
- }
- } else {
- Node right = buildTree(mid, getLevelArray(mid, midLocation + 1, midEnd, level), midLocation + 1, midEnd);
- root.right = right;
- }
- }
- return root;
- }
- // 功能 : 判断元素是根节点的左子树节点还是右子树节点
- // 参数 : target 为根节点 isLeft 在中序遍历结果中判断 children 是根节点的左子树还是右子树
- // 返回值 : 如果为左子树节点则为 true 否则为 false
- private boolean isLeft(int[] array, int target, int children) {
- boolean findC = false;
- for (int temp : array) {
- if (temp == children) {
- findC = true;
- } else if (temp == target) {
- return findC;
- }
- }
- return false;
- }
- // 功能: 将中序序列中 midBegin 与 midEnd 的元素依次从 level 中提取出来, 保持 level 中的元素顺序不变
- private int[] getLevelArray(int[] mid, int midBegin, int midEnd, int[] level) {
- int[] result = new int[midEnd - midBegin + 1];
- int curLocation = 0;
- for (int i = 0; i < level.length; i++) {
- if (contains(mid, level[i], midBegin, midEnd)) {
- result[curLocation++] = level[i];
- }
- }
- return result;
- }
- // 如果 array 的 begin 和 end 位置之间 (包括 begin 和 end) 含有 target, 则返回 true.
- private boolean contains(int[] array, int target, int begin, int end) {
- for (int i = begin; i <= end; i++) {
- if (array[i] == target) {
- return true;
- }
- }
- return false;
- }
来源: https://www.cnblogs.com/JefferyChenXiao/p/12246258.html