劍指offer編程題Java實現——面試題6重建二叉樹。本站提示廣大學習愛好者：（劍指offer編程題Java實現——面試題6重建二叉樹）文章只能為提供參考，不一定能成為您想要的結果。以下是劍指offer編程題Java實現——面試題6重建二叉樹正文
題目：
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷結果中都不含重復的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建出二叉樹並輸出他的根節點。
在二叉樹的前序遍歷中，第一個數字總是樹的根節點。在中序遍歷中，樹的根節點在序列的中間，左子樹的節點的值位於根節點的左邊，右子樹節點的值位於根節點值的右邊。
因此需要掃描中序遍歷序列才能找到很結點的值，由此可以找到左子樹的節點的個數和右子樹節點的個數，然後在前序遍歷序列中找到左子樹的根節點，再到中序遍歷序列中找到左子樹的左子樹和右子樹。依次遞歸。由於二叉樹的構造本身就是用遞歸實現的，所以重建二叉樹也用遞歸進行實現實很簡單的。
1 package Solution;
2
3 /**
4 * 劍指offer面試題6：重構二叉樹
5 * 題目：輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷結果中都不含重復的數字。
6 * 例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建出下圖的二叉樹並輸出他的根節點。
7 * 1
8 * / \
9 * 2 3
10 * / / \
11 * 4 5 6
12 * \ /
13 * 7 8
14 * @author GL
15 *
16 */
17 public class No6ReConstructBinaryTree {
18
19 public static void main(String[] args) {
20 int[] preOrder={1,2,4,7,3,5,6,8};
21 int[] inOrder={4,7,2,1,5,3,8,6};
22 BinaryTreeNode node=reConstruct(preOrder,inOrder);
23 printTree(node);
24 }
25 //二叉樹節點
26 public static class BinaryTreeNode{
27 int value;
28 BinaryTreeNode left;
29 BinaryTreeNode right;
30 }
31
32 /**
33 * 判斷輸入合法性
34 * @param preOrder
35 * @param inOrder
36 * @return
37 */
38 public static BinaryTreeNode reConstruct(int[] preOrder,int[] inOrder){
39 if(preOrder==null||inOrder==null||preOrder.length!=inOrder.length||preOrder.length<1)
40 return null;
41 return construct(preOrder,0,preOrder.length-1,inOrder,0,inOrder.length-1);
42 }
43
44 /**
45 * 根據前序遍歷和中序遍歷構建二叉樹
46 * @param preOrder 前序遍歷序列
47 * @param ps 前序遍歷開始位置
48 * @param pe 前序遍歷結束位置
49 * @param inOrder 中序遍歷序列
50 * @param is 中序遍歷開始位置
51 * @param ie 中序遍歷結束位置
52 * @return 構建的樹的根節點
53 */
54 public static BinaryTreeNode construct(int[] preOrder,int ps,int pe,int[] inOrder,int is,int ie){
55 //開始位置大於結束位置說明已經處理到葉節點了
56 if(ps>pe)
57 return null;
58 ///前序遍歷第一個數字為當前的根節點
59 int value=preOrder[ps];
60 //index為根節點在中序遍歷序列中的索引
61 int index=is;
62 while(index<=ie&&inOrder[index]!=value){
63 index++;
64 }
65 System.out.println("當前各參數的數值為->ps:"+ps+" pe:"+pe+" is："+is+" ie："+ie+" index："+index+" rootValue："+value);
66 //如果在整個中序遍歷中沒有找到根節點說明輸入的數據是不合法的
67 if(index>ie){
68 throw new RuntimeException("invalid input"+index);
69 }
70 BinaryTreeNode node=new BinaryTreeNode();
71 node.value=value;
72 //當前節點的左子樹的個數為index-is
73 //左子樹對應的前序遍歷的位置在preOrder[ps+1,ps+index-is]
74 //左子樹對應的中序遍歷的位置在inOrder[is,index-1]
75 node.left=construct(preOrder,ps+1,ps+index-is,inOrder,is,index-1);
76 //當前節點的右子樹的個數為ie-index
77 //右子樹對應的前序遍歷位置在preOrder[ps+index-is+1,pe]
78 //右子樹對應的中序遍歷位置在inOrder[index+1,ie]
79 node.right=construct(preOrder,ps+index-is+1,pe,inOrder,index+1,ie);
80 return node;
81 }
82 //中序遍歷遞歸打印
83 public static void printTree(BinaryTreeNode node){
84 if(node!=null){
85 printTree(node.left);
86 System.out.print(node.value+" ");
87 printTree(node.right);
88 }
89 }
90
91 }
