剑指Offer面试题6（Java版）：重建二叉树

超、凢脫俗 2022-07-16 04:53 190阅读 0赞

题目：输入某二叉树的前序遍历和中序遍历的结果，请重新构造出该二叉树。假设输入的前序遍历和中序遍历的结果中不包含重复的数字。例如输入的前序遍历序列为｛1，2，4，7，3，5，6，8｝和中序遍历为\{4,7,2,1,5,3,6,8\},则重建出二叉树并输出它的头结点。

在二叉树的前序遍历序列中，第一个数字总是树的根节点的值。但在中序遍历中，根节点的值在序列的中间，左子树的结点的值位于根节点的值的左边，而右子树的结点的值位于根节点的右边。因此我们需要扫描中序遍历序列，才能找到根节点的值。

如图所示，前序遍历序列的第一个数字1就是根节点的值。扫描中序遍历序列，就能确定根节点的值的位置。根据中序遍历的特点，在根节点的值1前面3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。

![Center][]

由于中序遍历序列中，有3个数字是左子树结点的值，因此左子树总共有3个左子结点。同样，在前序遍历的序列中，根节点后面的3个数字就是3个左子树结点的值，再后面的所有数字都是右子树结点的值。这样我们就在前序遍历和中序遍历两个序列中，分别找到了左右子树对应的子序列。

![Center 1][]

既然我们已经分别找到了左、右子树的前序遍历序列和中序遍历序列，我们可以用同样的方法分别去构建左右子树。也就是说，接下来的事情可以用递归的方法去完成。

我们使用Java语言来实现上面的代码：

首先构建二叉树代码：

**\[html\]**  [view plain][]   [copy][view plain]

1.  package utils;  
2.    
3.  public class BinaryTreeNode \{  
4.      public int value;  
5.      public BinaryTreeNode leftNode;  
6.      public BinaryTreeNode rightNode;  
7.        
8.      public BinaryTreeNode()\{  
9.            
10.     \}  
11.     public BinaryTreeNode(int value)\{  
12.         this.value = value ;  
13.         this.leftNode = null;  
14.         this.rightNode = null;  
15.     \}  
16.       
17. \}

重建二叉树代码：

**\[html\]**  [view plain][]   [copy][view plain]

1.  package swordForOffer;  
2.    
3.  /\*\*  
4.   \* @author JInShuangQi  
5.   \*  
6.   \* 2015年7月25日  
7.   \*/  
8.  import utils.BinaryTreeNode;  
9.    
10. public class E06ConstructBinaryTree \{  
11.     /\*\*  
12.      \*   
13.      \* @param preOrder 前序遍历数组  
14.      \* @param inOrder 中序遍历数组  
15.      \* @param length 数组长度  
16.      \* @return 根结点  
17.      \*/  
18.     public static BinaryTreeNode Construct(int\[\] preOrder, int\[\] inOrder,int length)\{  
19.         if (preOrder == null || inOrder == null || length **<**= 0) \{  
20.             return null;  
21.         \}  
22.         try \{  
23.             return ConstructCore(preOrder, 0, preOrder.length - 1, inOrder, 0,inOrder.length - 1);  
24.         \} catch (InvalidPutException e) \{  
25.             e.printStackTrace();  
26.             return null;  
27.         \}  
28.     \}  
29.   
30.     /\*\*  
31.      \*   
32.      \* @param PreOrder  
33.      \*            前序遍历序列  
34.      \* @param startPreIndex  
35.      \*            前序序列开始位置  
36.      \* @param endPreIndex  
37.      \*            前序序列结束位置  
38.      \* @param InOrder  
39.      \*            中序遍历序列  
40.      \* @param startInIndex  
41.      \*            中序序列开始位置  
42.      \* @param endInIndex  
43.      \*            中序序列结束位置  
44.      \* @return 根结点  
45.      \* @throws InvalidPutException  
46.      \*/  
47.     public static BinaryTreeNode ConstructCore(int\[\] preOrder,int startPreIndex, int endPreIndex,   
48.             int\[\] inOrder,int startInIndex, int endInIndex) throws InvalidPutException \{  
49.   
50.         int rootValue = preOrder\[startPreIndex\];  
51.         System.out.println("rootValue = " + rootValue);  
52.         BinaryTreeNode root = new BinaryTreeNode(rootValue);  
53.   
54.         // 只有一个元素  
55.         if (startPreIndex == endPreIndex) \{  
56.             if (startInIndex == endInIndex  
57.                     && preOrder\[startPreIndex\] == inOrder\[startInIndex\]) \{  
58.                 System.out.println("only one element");  
59.                 return root;  
60.             \} else \{  
61.                 throw new InvalidPutException();  
62.             \}  
63.         \}  
64.   
65.         // 在中序遍历中找到根结点的索引  
66.         int rootInIndex = startInIndex;  
67.   
68.         while (rootInIndex **<**= endInIndex && inOrder\[rootInIndex\] != rootValue) \{  
69.             ++rootInIndex;  
70.         \}  
71.   
72.         if (rootInIndex == endInIndex && inOrder\[rootInIndex\] != rootValue) \{  
73.             throw new InvalidPutException();  
74.   
75.         \}  
76.   
77.         int leftLength = rootInIndex - startInIndex;  
78.   
79.         int leftPreOrderEndIndex = startPreIndex + leftLength;  
80.   
81.         if (leftLength **>** 0) \{  
82.             // 构建左子树  
83.             root.leftNode = ConstructCore(preOrder, startPreIndex + 1,  
84.                     leftPreOrderEndIndex, inOrder, startInIndex,  
85.                     rootInIndex - 1);  
86.         \}  
87.   
88.         if (leftLength **<** **endPreIndex** - startPreIndex) \{  
89.             // 右子树有元素,构建右子树  
90.             root.rightNode = ConstructCore(preOrder, leftPreOrderEndIndex + 1,  
91.                     endPreIndex, inOrder, rootInIndex + 1, endInIndex);  
92.         \}  
93.         return root;  
94.     \}  
95.   
96.     static class InvalidPutException extends Exception \{  
97.   
98.         private static final long serialVersionUID = 1L;  
99.   
100.     \}  
101.   
102.     public static void printPreOrder(BinaryTreeNode root) \{  
103.         if (root == null) \{  
104.             return;  
105.         \} else \{  
106.             System.out.print(root.value + " ");  
107.         \}  
108.   
109.         if (root.leftNode != null) \{  
110.             printPreOrder(root.leftNode);  
111.         \}  
112.   
113.         if (root.rightNode != null) \{  
114.             printPreOrder(root.rightNode);  
115.         \}  
116.     \}  
117.   
118.     public static void main(String\[\] args) throws Exception\{  
119.         E06ConstructBinaryTree test=new E06ConstructBinaryTree();  
120.         int\[\] preOrder=\{1,2,4,7,3,5,6,8\};  
121.         int\[\] inOrder=\{4,7,2,1,5,3,8,6\};  
122.          printPreOrder(Construct(preOrder, inOrder, preOrder.length));  
123.     \}  
124. \}

在函数ConstructCore中，我们先根据先序遍历的第一个数字创建根节点，接下来在中序遍历中找到根节点的位置，这样就能确定左右子树节点的数量。在前序遍历和中序遍历的序列中划分左右子树节点的值之后，我们就可以递归调用函数ConstructCore，去分别构建它的左右子树。

[Center]: /images/20220716/4f7a13d203b641539c4cbc977269854f.png
[Center 1]: /images/20220716/b7b9e65252894f84a332ed786b5719fb.png
[view plain]: http://blog.csdn.net/jsqfengbao/article/details/47088947#