本題思路根據Carl大佬整理，大家感興趣的去關注一波。如果你想提升算法能力，只要跟住代碼隨想錄每天題目的節奏，定會融會貫通，算法能力穩穩的提升一個臺階！

一、?先如何根據兩個順序構造?個唯?的?叉樹?

1、以中序和后序遍歷來說：

就是以 后序數組的最后?個元素為切割點，先切中序數組，然后根據中序左數組，反過來在切后序數組。?層?層切下去，每次后序數組最后?個元素就是節點元素。

1、接下來想到用遞歸法
(1)、如果后序數組大小為0，說明是空節點。返回NULL。
(2)、如果不為空，取后序數組最后一個元素作為節點元素。同時再判斷一下后序數組大小是不是為1，為1說明是葉子節點直接返回。
(3)、接著找到后序數組最后一個元素在中序數組的位置，作為切割點。
(4)、把中序數組切割成中序左數組和中序右數組。
(5)、把后序數組切割成后序左數組和后序右數組。
(6)、遞歸處理左區間和右區間。

注意事項：
1、確定切割標準，找好邊界值。
2、先切中序數組，因為切割點是后序數組最后一個元素。
3、后序數組沒有明確的切割點，但是要記得中序數組大小一定等于后序數組大小。
現在我們把中序數組切成了中序左數組和中序右數組，那么后序數組就可以按照中序左數組的大小來切割，得到后序左數組和后序右數組。

遞歸法(容器分割)

class Solution{ private:TreeNode* traversal(vector<int>&inorder,vector<int>&postorder) {//第一步，判斷后序數組大小是否為0if(postorder.size()==0) return NULL;//第二步，找到后序遍歷數組最后?個元素，就是當前的中間節點，接著判斷是不是葉子節點int rootValue=postorder[postorder.size()-1];TreeNode* root=newTreeNode(rootValue);if(postorder.size()==1) return root;//第三步，找到中序遍歷的切割點int delimiterIndex;//1從0開始，因為是容器里面裝著數組for(delimiterIndex=0;delimiterIndex<inorder.size();delimiterIndex++) {if(inorder[delimiterIndex]==rootValue)break;}//第四步，切割中序數組//左閉右開區間：[0, delimiterIndex)vector<int> leftInorder(inorder.begin(),inorder.begin()+delimiterIndex);// [delimiterIndex + 1, end)vector<int> rightInorder(inorder.begin()+delimiterIndex+1,inorder.end() );// postorder舍棄末尾元素postorder.resize(postorder.size()-1);//第五步，切割后序數組//依然左閉右開，注意這?使?了左中序數組??作為切割點，[0, leftInorder.size)vector<int> leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());// [leftInorder.size(), end)vector<int> rightPostorder(postorder.begin()+leftInorder.size(),postorder.end());root->left=traversal(leftInorder,leftPostorder);root->right=traversal(rightInorder,rightPostorder);return root; } public:TreeNode* buildTree(vector<int>&inorder,vector<int>&postorder{if(inorder.size()==0||postorder.size()==0) return NULL;returntraversal(inorder,postorder);} };

如上的代碼性能并不好，因為每層遞歸都定義了新的vector（就是數組），既耗時?耗空間，但上?的代碼是最好理解的。

遞歸法（下表索引分割）

思路是?樣的，只不過不?重復定義vector了，每次?下表索引來分割

class Solution{ private:// 中序區間： [inorderBegin, inorderEnd)，后序區間[postorderBegin, postorderEnd)TreeNode* traversal(vector<int>& inorder,int inorderbegin,int inorderend,vector<int>& postorder,int postorderbegin,int postorderend){if(postorderbegin==postorderend) return nullptr;int rootValue=postorder[postorderend-1];TreeNode* root=new TreeNode(rootValue);if(postorderend-postorderbegin==1) return root;//找到分割點在中序數組的位置int delimiterIndex;for(delimiterIndex=inorderbegin;delimiterIndex<inorderend;delimiterIndex++){ ///1 ,注意標記法的開始和結束if(inorder[delimiterIndex]==rootValue) break;}//切割中序數組//中序左數組,左閉右開[leftInorderBegin, leftInorderEnd)int leftInorderbegin=inorderbegin;//中序左數組的開始位置int leftInorderend=delimiterIndex;//中序左數組結束位置//中序右數組,左閉右開[rightInorderBegin, rightInorderEnd)int rightInorderbegin=delimiterIndex+1;//中序右數組開始位置int rightInorderend=inorderend;//根據中序左數組大小切割后序數組//后序左數組,左閉右開[leftPostorderBegin, leftPostorderEnd)int leftPostorderbegin=postorderbegin;int leftPostorderend=postorderbegin+(delimiterIndex-inorderbegin);///2//后序右數組,左閉右開[rightPostorderBegin, rightPostorderEnd)int rightPostorderbegin=postorderbegin+(delimiterIndex-inorderbegin);///3int rightPostorderend=postorderend-1;///4 排除最后?個元素，已經作為節點了root->left=traversal(inorder,leftInorderbegin,leftInorderend,postorder,leftPostorderbegin,leftPostorderend);root->right=traversal(inorder,rightInorderbegin,rightInorderend,postorder,rightPostorderbegin,rightPostorderend);return root;} public:TreeNode* buildTree(vector<int>&inorder,vector<int>& postorder){if(inorder.size()==NULL||postorder.size()==NULL) return nullptr;return traversal(inorder,0,inorder.size(),postorder,0,postorder.size());} };

2、以前序和中序遍歷

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution { private:TreeNode* traversal(vector<int>& preorder,int preorderBegin,int preorderEnd,vector<int>& inorder,int inorderBegin,int inorderEnd ){if(preorderBegin==preorderEnd) return NULL;int rootValue=preorder[preorderBegin];TreeNode* root=new TreeNode(rootValue);if(preorderEnd-preorderBegin==1) return root;int delimiterIndex;for(delimiterIndex=inorderBegin;delimiterIndex<inorderEnd;delimiterIndex++){if(inorder[delimiterIndex]==rootValue) break;}//切割中序數組int leftInorderBegin=inorderBegin;int leftInorderEnd=delimiterIndex;int rightInorderBeigin=delimiterIndex+1;int rightInorderEnd=inorderEnd;//切割前序數組int leftPreorderBegin=preorderBegin+1;int leftPreorderEnd=preorderBegin+(delimiterIndex-inorderBegin)+1;int rightPreorderBeigin=preorderBegin+(delimiterIndex-inorderBegin)+1;int rightPreorderEnd=preorderEnd;root->left=traversal(preorder,leftPreorderBegin,leftPreorderEnd,inorder,leftInorderBegin,leftInorderEnd);root->right=traversal(preorder,rightPreorderBeigin,rightPreorderEnd,inorder,rightInorderBeigin,rightInorderEnd);return root;} public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size()==NULL||inorder.size()==NULL) return NULL;return traversal(preorder,0,preorder.size(),inorder,0,inorder.size());} };

總結

以上是生活随笔為你收集整理的如何根据两个顺序构造⼀个唯⼀的⼆叉树？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。