题目描述
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>
分享到:
閱讀更多 我的架構師之路 的文章
