106.從中序與后序遍歷序列構造二叉樹

力扣題目鏈接(opens new window)

根據一棵樹的中序遍歷與后序遍歷構造二叉樹。

注意: 你可以假設樹中沒有重復的元素。

例如，給出

• 中序遍歷 inorder = [9,3,15,20,7]
• 后序遍歷 postorder = [9,15,7,20,3] 返回如下的二叉樹：

思路

根據中序遍歷和后序遍歷構造二叉樹的理論知識：首先由后序遍歷確定根節點（從尾開始遍歷），在中序遍歷找到其相應的左右子節點（左中右），反復這個操作。

根據理論知識我們轉換成實際操作。

• 取Postorder的最后一個元素
  • 若Postorder的數組為空，則返回null
• 確定根元素在Inorder中的位置
• 開始分割
  • 先分割中序
    • 左畢右開
  • 后分割后序
    • 左閉右開
• 遞歸
• 返回

代碼如下：

class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(postorder.empty())return nullptr;// 當前根節點int rootValue = postorder[postorder.size()-1];TreeNode* root = new TreeNode(rootValue);// 找根節點在中序的位置int deliIndex;for(deliIndex = 0;deliIndex<inorder.size();deliIndex++){if(inorder[deliIndex] == rootValue)break;}//分割中序左右子結點vector<int> leftInorder(inorder.begin(),inorder.begin() + deliIndex);vector<int> rightInoder(inorder.begin() + deliIndex + 1, inorder.end());//分割前序左右子節點postorder.resize(postorder.size()-1);vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());root->left = buildTree(leftInorder,leftPostorder);root->right = buildTree(rightInoder,rightPostorder);return root;}
};

Tips：切割后序數組的時候，可以根據中序分割的大小進行分割，因為其大小一定是一致的。

優化

第一個優化：在找根節點分別在后序和中序中的位置時，可以使用map進行編號。

第二個優化：進行分割時，只需分割中序數組即可。

class Solution {
private:int cus_pos;unordered_map<int,int>in;
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {cus_pos=postorder.size()-1;int num=0;// 對inorder進行編號for(auto &n:inorder){in[n]=num++;}int left=0,right=inorder.size()-1;return dis(left,right,inorder,postorder);}TreeNode* dis(int left,int right,vector<int>& inorder, vector<int>& postorder){if(left>right)return nullptr;int root_val=postorder[cus_pos--];int index=in[root_val];TreeNode* p=new TreeNode(root_val);// 分割數組p->right=dis(index+1,right,inorder,postorder);p->left=dis(left,index-1,inorder,postorder);return p;}
};r,postorder);p->left=dis(left,index-1,inorder,postorder);return p;}
};