#資料結構與算法學習筆記#劍指Offer4：先序周遊+中序周遊重建二叉樹（Java、C/C++）

2018.7.30     《劍指Offer》從零單刷個人筆記整理（66題全）目錄傳送門​​​​​​​

思路其實和之前做過的#資料結構與算法學習筆記#PTA11：先序周遊+中序周遊轉後序周遊/二叉樹非遞歸周遊/二叉樹棧周遊（JAVA）是一樣的。

題目描述

輸入某二叉樹的前序周遊和中序周遊的結果，請重建出該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建二叉樹并傳回。

JAVA實作：

/**
 * 
 * @author ChopinXBP
 * 題目描述
 * 輸入某二叉樹的前序周遊和中序周遊的結果，請重建出該二叉樹。
 * 假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。
 * 例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建二叉樹并傳回。
 *
 */


public class ReconstructBinaryTree {


	public static class TreeNode{
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x){val = x;}
	}

	private static int[]pre = {1,2,4,7,3,5,6,8};
	private static int[]in = {4,7,2,1,5,3,8,6};
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeNode BinTree = ReConstructBinaryTree(pre, in);
		System.out.println("Over");
	}

	//根據前序周遊與中序周遊重構二叉樹
	//注意：原題中pre與in并非全局變量，需要對函數參數進行相應修改
	public static TreeNode ReConstructBinaryTree(int []pre, int[] in){
		TreeNode BinTree = new TreeNode(pre[0]);
		
		int flag = 0;
		int head = 0;
		int tail = in.length-1;
		int root = Find(pre[0]);
		
		if(root != -1){
			ReConstructSolution(BinTree, flag, head, tail, root);
		}
				
		return BinTree;
	}
	
	//遞歸重構二叉樹
	private static void ReConstructSolution(TreeNode tree, int flag, int head, int tail, int root){
		//左右子樹均有，先遞歸重建左子樹，後遞歸重建右子樹
		if(root != head && root!= tail){
			int leftroot = pre[flag+1];
			tree.left = new TreeNode(leftroot);
			ReConstructSolution(tree.left, flag+1, head, root-1, Find(leftroot));
			
			int rightroot = pre[flag+(root-head)+1];
			tree.right = new TreeNode(rightroot);
			ReConstructSolution(tree.right, flag+(root-head)+1, root+1, tail, Find(rightroot));
		}
		//隻有右子樹，遞歸重建右子樹
		else if(root == head && root != tail){
			int rightroot = pre[flag+(root-head)+1];
			tree.right = new TreeNode(rightroot);
			ReConstructSolution(tree.right, flag+(root-head)+1, root+1, tail, Find(rightroot));
		}
		//隻有左子樹，遞歸重建左子樹
		else if(root == tail && root != head){
			int leftroot = pre[flag+1];
			tree.left = new TreeNode(leftroot);
			ReConstructSolution(tree.left, flag+1, head, root-1, Find(leftroot));
		}
		
	}
	
	//傳回中序周遊數組某一進制素所在位置
	private static int Find(int data){
		for(int i = 0;i<in.length;i++){
			if(in[i] == data)return i;
		}
		return -1;
	}


	
}
           

C++實作參考：

/**
  
     * Definition for binary tree
  
     * struct TreeNode {
  
     *     int val;
  
     *     TreeNode *left;
  
     *     TreeNode *right;
  
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  
     * };
  
     */
  
    class Solution {
  
    public:
  
        struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
  
            int inlen=in.size();
  
            if(inlen==0)
  
                return NULL;
  
            vector<int> left_pre,right_pre,left_in,right_in;
  
            //建立根節點，根節點肯定是前序周遊的第一個數
  
            TreeNode* head=new TreeNode(pre[0]);
  
            //找到中序周遊根節點所在位置,存放于變量gen中
  
            int gen=0;
  
            for(int i=0;i<inlen;i++)
  
            {
  
                if (in[i]==pre[0])
  
                {
  
                    gen=i;
  
                    break;
  
                }
  
            }
  
            //對于中序周遊，根節點左邊的節點位于二叉樹的左邊，根節點右邊的節點位于二叉樹的右邊
  
            //利用上述這點，對二叉樹節點進行歸并
  
            for(int i=0;i<gen;i++)
  
            {
  
                left_in.push_back(in[i]);
  
                left_pre.push_back(pre[i+1]);//前序第一個為根節點
  
            }
  
            for(int i=gen+1;i<inlen;i++)
  
            {
  
                right_in.push_back(in[i]);
  
                right_pre.push_back(pre[i]);
  
            }
  
            //和shell排序的思想類似，取出前序和中序周遊根節點左邊和右邊的子樹
  
            //遞歸，再對其進行上述所有步驟，即再區分子樹的左、右子子數，直到葉節點
  
           head->left=reConstructBinaryTree(left_pre,left_in);
  
           head->right=reConstructBinaryTree(right_pre,right_in);
  
           return head;
  
        }
  
    };
           

#Coding一小時，Copying一秒鐘。留個言點個贊呗，謝謝你#