《剑指Offer》面试题六之重建二叉树

2019-11-06 06:55:54

字体：大中小

来源：转载

供稿：网友

题目描述

输入某二叉树的前序和中序遍历的结果，请重建该二叉树。

问题分析

假设有一二叉树前序遍历结果：1，2，4，7，3，5，6，8 中序遍历结果：4，7，2，1，5，3，8，6

说明：在这里我是默认你了解二叉树的三种遍历过程，如下图：

我们使用下面的一系列的图片来显示重建二叉树的过程：

首先，前序遍历的第一个数位整个树的根节点，如下图：第一步

第二个数为 2 ，如下：第二步

第三个数为4，如下：第三步

第四个数为7，如下：第四步

第五个数为 3 ，如下：第五步

第六个数为 5，如下：第六步第七个数为 6，如下：第七步

最后一个数为 8，如下：第八步

以上就是对这个例子的图示过程了，接下来用代码进行实现：

代码实现

package question;import java.util.*;/** * 作者：白芷时间：2017/3/5 说明：二叉树的重建 */class TreeNode { PRotected int data; protected TreeNode left; // 二叉树左结点 protected TreeNode right; // 二叉树右结点 public static Boolean flag=true;// 标识是否输入合法 public TreeNode reBuildTree(int[] beforeOrder, int[] inOrder, int nodeNum) throws Exception { try { int cur = 0; while (beforeOrder[cur] == 9999) { // 找到数组中第一个不为 9999 的数 cur++; if (cur == beforeOrder.length) return null; } TreeNode node = null; for (int j = 0; j < nodeNum; j++) { if (inOrder[j] == beforeOrder[cur]) { node = TreeNode.createTreeNode(beforeOrder[cur]); beforeOrder[cur] = 9999; // 设置为 9999 表示这个数已经用过了， // 也可以设置一个数据结构(链表),用一个字段标识是否已经使用 node.left = reBuildTree(beforeOrder, Arrays.copyOfRange(inOrder, 0, j), j); // 两次递归 node.right = reBuildTree(beforeOrder, Arrays.copyOfRange(inOrder, j + 1, nodeNum), nodeNum - j - 1); break; } if (j == nodeNum - 1)// 说明未 break; { if(TreeNode.flag)System.out.println("No"); TreeNode.flag=false; throw new Exception(); } } return node; } catch (Exception e) { return null; } } public static TreeNode createTreeNode(int data) { TreeNode node = new TreeNode(); node.data = data; node.left = null; node.right = null; return node; } // 后序遍历代码 public void printAfterOrder(TreeNode root) { if (root != null) { printAfterOrder(root.left); printAfterOrder(root.right); System.out.print(root.data + " "); } }}public class Question6 { public static void main(String[] args) { int[] beforeOrder; // 前序遍历数组 int[] inOrder; // 中序遍历数组 int nodeNum = 0; // 二叉树的节点数 Scanner input = new Scanner(System.in); while (true) { try { nodeNum = input.nextInt(); beforeOrder = new int[nodeNum]; inOrder = new int[nodeNum]; for (int i = 0; i < nodeNum; i++) { beforeOrder[i] = input.nextInt(); } for (int i = 0; i < nodeNum; i++) { inOrder[i] = input.nextInt(); } TreeNode originalTree = new TreeNode(); originalTree = originalTree.reBuildTree(beforeOrder, inOrder, nodeNum); if(TreeNode.flag){ originalTree.printAfterOrder(originalTree); System.out.println(); } TreeNode.flag=true; } catch (Exception e) { break; } } }}

上面的算法将该二叉树的后序遍历打印出来了，能AC九度OJ上面的题： http://ac.jobdu.com/problem.php?pid=1385

上一篇：504. Base 7

下一篇：Array