題目描述

在這里插入圖片描述

原理分析

（1）大致思路

下面講解一下，前序遍歷+中序遍歷如何確定一個唯一的二叉樹，關于二叉樹的基本知識，請看二叉樹的基本操作及聯系，對此就不再過多重復，對于前序遍歷順序：根、左子樹、右子樹；對于中序的遍歷順序：左子樹、根、右子樹，所以通過前序遍歷，我們獲取前序第一個結點就是這個樹的根，再在中序遍歷中找到該結點的位置，在中序中，根的左邊全部的是屬于根左子樹的結點，根的右邊全是屬于根的右子樹的結點，
詳細如圖：
做完第一步之后，我們會發現，我們目前只具體確定了哪一個是根節點，哪些結點分別屬于左右子樹，但是由于樹的遞回特性，屬于左子樹的結點仍然符合前序遍歷，中序遍歷特點的，所以我們就是需要對剛剛分離出來的兩部分分別再次用上述的方法，確定根節點，確定哪些結點屬于左子樹，哪些結點屬于右子樹，一次類推，直到結束，這就是這道題的大致思路，

（2）細節闡述

這道題還是有不少值得思考的地方，
1、我們如何表示哪些結點是屬于左子樹，右子樹？
答：前序、中序的給出都vector，所以我們可以通過下標確定范圍來做到，前序：【根，左子樹，右子樹】，中序：【左子樹，根，右子樹】，他們都是三種類別結點都是集中在一起，很好區分，
2、遞回的結束條件是什么？
答：這個還是要結合具體代碼分析，目前可以確定的是，當我們控制范圍時，如果出現范圍不合法（不存在）的情況就說明已經沒有左子樹或者右子樹了，就要回傳，

代碼實作

注：一般在我的題解中，范圍控制，代碼這樣書寫的原因都會通過注釋的方式寫在對應代碼旁邊，幫助讀者理解分析代碼，這樣更有針對性，因此，如果讀者對于前面的題目分析有疑惑或者不理解的地方，請仔細閱讀代碼及旁邊注釋，一定會對你有所啟發，幫助你的理解！！

（1）主函式

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	//_buildTree本題因為需要遞回實作，因此需要借助一個遞回函式，
       return _buildTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }

我在這里要詳細說明一下這個遞回函式的各個引數及作用
第一個引數：就是前序遍歷的vector，沒有太多需要解釋的
第二個引數：preStart，就是在子問題種前序的起始位置，詳細的說，就是我們在確定根以后，我們就要遞回左右子樹，左右子樹的起始位置是哪里就要確定，
第三個引數：preEnd：就是在子問題種前序的終止位置，這樣就保證preStart與preEnd之間是子問題的結點序列，
第四個引數就是中序遍歷的vector
第五個引數：inStart，就是在子問題中中序遍歷的起始位置
第六個引數：inEnd，就是在子問題種中序遍歷的結束位置

（2）遞回函式

	TreeNode* _buildTree(vector<int>& preorder,int preStart,int preEnd,vector<int>&inorder,int inStart,int inEnd)
    {
        if(preStart>preEnd)
        {
            return nullptr;
        }
        //我們可以直接確定根節點，所以我們首先創建出根節點
        TreeNode* root = new TreeNode(preorder[preStart]);
        //找到根節點后，我們拿著根節點的值在中序遍歷中找到對應位置，區分左右子樹
        for(int i=inStart;i<=inEnd;i++)
        {
        	//找到根節點所在的中序遍歷的位置
            if(inorder[i] == preorder[preStart])
            {
            	//由于遞回函式完成子問題樹的構建，所有讓大問題的root左右子樹分別鏈接即可
                root->left = _buildTree(preorder,preStart+1,preStart+i-inStart,inorder,inStart,i-1);
                root->right = _buildTree(preorder,preStart+i-inStart+1,preEnd,inorder,i+1,inEnd);
            }
        }
        return root;
    }

引數區間的決定

關鍵就是在遞回子問題的時候傳引數是多少，

size:size是左子樹中的結點個數所以size = i-inStart
所以：root->left = _buildTree(preorder,preStart+1,preStart+i-inStart,inorder,inStart,i-1);
xxxxxxroot->right = _buildTree(preorder,preStart+i-inStart+1,preEnd,inorder,i+1,inEnd);
讀者自行比較即可理解

遞回結束的條件

接下來就是判斷如何結束遞回，就是遞回函式中的第一個if，之前我們提到過，如果子問題子樹的區間不存在就可以結束回圈了，那么怎么才叫不存在呢？
我們剛付訓得了每一個子樹的前序的范圍【preStart，preEnd】，如果preStart==preEnd時候，就說明子樹還有一個結點，仍然需要回圈，但是有沒有可能preStart>preEnd呢？答案是肯定的，我們發現遞回子問題的時候preStart = preStart+1，preStart不斷增大，而遞回子問題時preEnd = preStart+size-1，
分析比較得：當子樹只有一個結點（size == 1）是，preStart == preEnd，再遞回一次后，size == 0，因此preStart > preEnd，就說明沒有子樹了，可以回傳nullptr了，
所以得到代碼：if (preStart>preEnd) return nullptr;

總結

xxxx看到二叉樹問題，我們首相應該想到的就是函式遞回，因而二叉樹具有很好的“遞回特性”，每一個子樹都是二叉樹，都滿足樹的特性，子問題具有一樣的特性就可以使用遞回演算法，其次我們應該明確知道，二叉樹的“前、中、后，層序遍歷”，并且知道他們之間的關系聯系以及區別，在有以上的思想以及儲備知識后，我們就可以寫出具有一定思路的代碼邏輯，這道題還有一個比較重要的地方就是控制子問題的前序、中序vector的范圍界限，真正保證子問題與原問題的統一
xxxx這就是這道題的完整決議，如果大家有更好的思路，或者我代碼中可優化的地方，請指出，我一定虛心學習，希望我們一起學習，一起進步！！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299674.html

標籤：其他

上一篇：資料結構：順序表實作增刪查改基本功能

下一篇：??兩萬字《演算法 + 資料結構》如何開始??