題目描述
105. 從前序與中序遍歷序列構造二叉樹
根據一棵樹的前序遍歷與中序遍歷構造二叉樹。
注意:
你可以假設樹中沒有重複的元素。
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3
/ \\
9 20
/ \\
15 7
鏈接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
題目分析
時間複雜度：O(N)
前序遍歷 每個節點都是root元素；
利用中序把數組劃分成左右兩個，定出左右子樹在中序中的左右界
邊界分析：
元素沒有重複元素：
參考答案
/**
*
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector& preorder, vector & inorder) {
//數據合法性檢驗
if (preorder.size() != inorder.size()) return NULL;
//遞歸構造一顆樹
return helper(preorder, 0,preorder.size()-1, \\
inorder,0,inorder.size()-1);
}
TreeNode* helper(vector& preorder,int pStart,int pEnd,vector & inorder,int iStart,int iEnd)
{ //cout<< pEnd << " "<< pStart << " " <<iend>
if (pEnd < pStart || iEnd < iStart)
{
return NULL;
}
TreeNode* root =new TreeNode(preorder[pStart]);
//根據preorder[pStart]拆分左右子樹，並且計算範圍
int mid=iStart ;
// while (inorder[iStart] != root->val) //iStart 位置不能發生變化，變化的mid
while (inorder[mid] != root->val)
{
mid++;
}
int left = mid-iStart;
//對各自範圍構造一棵樹
root->left = helper(preorder,pStart+1,pStart+left,inorder,iStart,mid-1);
root->right = helper(preorder,pStart+left+1,pEnd,inorder,mid+1,iEnd);
return root;
}
};
/<iend>
分享到:
閱讀更多 我的架構師之路 的文章
