劍指offer：4.重建二叉樹
摘要：
題目
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重複的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹並返回。 牛客網oj地址
樣例
給定：
前序...
題目
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重複的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹並返回。 牛客網oj地址
樣例
給定： 前序遍歷是：[3, 9, 20, 15, 7] 中序遍歷是：[9, 3, 15, 20, 7] 返回：[3, 9, 20, null, null, 15, 7, null, null, null, null] 返回的二叉樹如下所示： 3 / \ 920 /\ 157
解題思路
這題使用遞迴的思路進行解題，首先根據前序遍歷我們可以確定根節點的值（前序遍歷的第一個數），又因為所有值都是不重複的所以我們可以在中序遍歷中唯一確定這個值的位置。同時根據中序遍歷的定義我們可以知道這個位置的左邊為二叉樹左子樹中序遍歷的結果，右邊為右子樹中序遍歷的結果。這樣我們可以得到左子樹節點的數量和右子樹節點的數量，根據前序遍歷的定義在前序遍歷中第一個值後面的部分分別為左子樹前序遍歷的結果和右子樹前序遍歷的結果。現在我們分別有了左子樹和右子樹前序和中序遍歷的結果，繼續遞迴求解，終止條件為前序遍歷為空。具體程式碼如下所示：
class Solution {
private:
vector<int> pre;
vector<int> vin;
unordered_map<int,int> theMap;
public:
TreeNode *reConstructBinaryTree(vector<int> pre, vector<int> vin) {
this->pre=pre;
this->vin=vin;
int length=vin.size();
//因為需要不斷查詢根節點在中序遍歷中的位置，所以使用hashmap將查詢複雜度降到O（1）
for (int i = 0; i < length; ++i) {
theMap[vin[i]]=i;
}
return dfs(0,length-1,0,length-1);
}
TreeNode * dfs(int pl,int ph,int vl,int vh){
if(pl>ph)
return nullptr;
TreeNode * root=new TreeNode(pre[pl]);
int vinIndex=theMap[pre[pl]];
int leftLength=vinIndex-vl; //計算左子樹的節點數量
root->left=dfs(pl+1,pl+leftLength,vl,vinIndex-1);
root->right=dfs(pl+leftLength+1,ph,vinIndex+1,vh);
return root;
}
};
類似題目
leetcode：106. 從中序與後序遍歷序列構造二叉樹 。解題思路完全一致，ac程式碼如下。
class Solution {
private:
unordered_map<int,int> theMap;
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int length=inorder.size();
for (int i = 0; i < length; ++i) {
theMap[inorder[i]]=i;
}
return dfs(postorder,0,length-1,0,length-1);
}
TreeNode * dfs(const vector<int> & postorder,int pl,int ph,int il,int ih){
if(pl>ph)
return nullptr;
TreeNode * root=new TreeNode(postorder[ph]);
int vinIndex=theMap[postorder[ph]];
int rightLength=ih-vinIndex;
root->left=dfs(postorder,pl,ph-rightLength-1,il,vinIndex-1);
root->right=dfs(postorder,ph-rightLength,ph-1,vinIndex+1,ih);
return root;
}
};
本 作品 由 尹傲雄 採用 知識共享署名-非商業性使用-相同方式共享 4.0 國際許可協議 進行許可。