劍指offer重構二叉樹超詳細講解

題目：輸入某二叉樹的前序周遊和中序周遊的結果，請重構該二叉樹，假設輸入的前序周遊和中序周遊的結果不含重複的數字。例如

前序周遊{1，2，4，7，3，5，6，8}

中序周遊{4，7，2，1，5，3，8，6}

顯然此二叉樹應該為

///              1
    ///           /     \
    ///          2       3  
    ///         /       / \
    ///        4       5   6
    ///         \         /
    ///          7       8  
           

前序周遊序列的第一個數字1就是根節點。掃描中序周遊，就能确定根節點的位置。

根據中序周遊的特點：

在根節點前面的數字4 7 2都是左子樹節點的值

在根節點1後面的數字5 3 8 6都是右子樹的值

我們可以用遞歸的方法去完成重構二叉樹

我們先根據前序周遊的第一個數字建立根節點，接下裡在中序周遊序列找到根節點位置，這樣能确定左右子樹節點數量。這樣就能遞歸調用分别取建構他們的左右子樹。

過程如下：

1. Pre 1 2 4 7 3 5 6 8

   Ord 4 7 2 1 5 3 8 6

   将根節點1分成 左樹4 7 2 和 右數 5 3 8 6

2. 建構1的左子樹

   Pre 2 4 7

   Ord 4 7 2

   建構2的左子樹

   Pre 4 7

   Ord 4 7

   建構4的右子樹

   Pre 7

   Ord 7

   根節點4右樹建構完成

   中序周遊結果 4 7

   根節點2左樹建構完成

   中序周遊結果 4 7 2

   根節點1左樹建構完成

3. 建構1的右子樹

   Pre 3 5 6 8

   Ord 5 3 8 6

   建構3的左子樹

   Pre 5

   Ord 5

   3節點左樹完成

   中序周遊結果 5 3

   建構3的右子樹

   Pre 6 8

   Ord 8 6

   建構6的左子樹

   Pre 8

   Ord 8

   根節點6左樹建構完成

   中序周遊結果 8 6

   根節點3右樹建構完成

   中序周遊結果 5 3 8 6

   根節點1右樹建構完成

   中序周遊結果 4 7 2 1 5 3 8 6

樹已創造完成。下面上代碼：

#include<bits/stdc++.h>
using namespace std;

struct BTNode{
 int value;
 BTNode* left;
 BTNode* right;
};

void print(BTNode* head)
{
 if(head==NULL)return;
 print(head->left);
 cout<<head->value<<" ";
 print(head->right);
}

BTNode* ConstructCore
(int* startPre,int* endPre,int* startOrd,int* endOrd)
{
 cout<<" 開始  前序周遊區間"<<*startPre<<"->"<<*endPre<<"  ||  中序周遊區間"<<*startOrd<<"->"<<*endOrd<<endl;
 //前序周遊的第一個數字就是根節點 
 int rootvalue=startPre[0];
 BTNode* root=new BTNode();
 root->value=rootvalue;
 root->left=root->right=NULL;
 //如果隻有一個節點就傳回 
 if(startPre==endPre)
 {
   return root;
 }
 //中序周遊找到根節點的位置，其左為左子樹，右為右子樹 
 int* rootoder=startOrd;
 while(rootoder<=endOrd&&*rootoder!=rootvalue)
 rootoder++;
  
 
 int leftLenth=rootoder-startOrd;//左子樹總長度 
 int* leftPreend=startPre+leftLenth;//左子樹末尾 
 if(leftLenth>0)
 {
  cout<<"建構左子樹:"; 
  root->left= ConstructCore(startPre+1,leftPreend,startOrd,rootoder-1);
 }
 if(leftLenth<endPre-startPre)
 {
  cout<<"建構右子樹:"; 
  root->right=ConstructCore(leftPreend+1,endPre,rootoder+1,endOrd);
 }
 cout<<"中序周遊root:"; 
 print(root);
 cout<<endl;
 return root;
}

BTNode* Construct(int* preoder,int* inorder,int lenth)
{
  cout<<"重建二叉樹:"; 
 return ConstructCore(preoder,preoder+lenth-1,inorder,inorder-1+lenth);
}
int main()
{ 
 int pre[8]={1,2,4,7,3,5,6,8};
 int ord[8]={4,7,2,1,5,3,8,6};
 cout<<"前序周遊為：1 2 4 7 3 5 6 8"<<endl;
 cout<<"中序周遊為：4 7 2 1 5 3 8 6"<<endl;
 BTNode* head=Construct(pre,ord,8);
  return 0;
}




           

代碼運作結果：