問題描述
根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。
注意:
你可以假設(shè)樹中沒有重復(fù)的元素。
Example
輸入：前序遍歷 preorder = [3,9,20,15,7]
返回如下的二叉樹：
中序遍歷 inorder = [9,3,15,20,7]
題目鏈接：105. 從前序與中序遍歷序列構(gòu)造二叉樹 (難度:中等)
思路
樹的先序遍歷順序?yàn)?NLR，中序遍歷順序?yàn)?LNR。因此，我們可以采用分治的思想，以先序序列 preorder 中的 preorder[0] 為樹的根節(jié)點(diǎn) root，然后通過 root 我們可以中序序列劃分為左右兩棵子樹，分別對(duì)左右兩棵子樹遞歸處理，即可完成建樹，如下圖所示
選擇根節(jié)點(diǎn)，并劃分左右子樹
處理右子樹
代碼
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
}
// l_pre 和 r_pre 代表當(dāng)前子樹在 preorder 中的左右邊界
// l_in 和 r_in 代表當(dāng)前子樹在 inorder 中的左右邊界
TreeNode* buildTree(vector<int>& preorder, int l_pre,int r_pre,vector<int>& inorder,int l_in,int r_in) {
if(l_pre > r_pre || l_in > r_in)
return NULL;
TreeNode* root = new TreeNode(preorder[l_pre]);
int pos = l_in;
while(inorder[pos] != preorder[l_pre]){
pos++;
}
root->left = buildTree(preorder, l_pre + 1, l_pre + pos - l_in, inorder, l_in, pos - 1);
root->right = buildTree(preorder, pos - l_in + l_pre + 1, r_pre, inorder, pos + 1, r_in);
return root;
}
};
