方法一:直接使用复制的数据递归:O(n)时间,O(n)空间,不计算递归栈空间;
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ /** 我觉得可以尝试递归,因为具有子结构,对于前序遍历序列,取第一个元素为root,在inorder中找打root,则对root左边的元素以及右边元素的inorder子序列和同样长度的preorder序列执行同样的操作; 递归边界:preorder没有元素; **/ class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { //递归边界 if(preorder.size()==0) return NULL; //递归数据准备:将preorder和inorder划分为4个子串; int v=preorder[0]; int index=0; vector<int> subpre_r,subpre_l,subin_r,subin_l; for(int i=0;i<preorder.size();i++) if(inorder[i]==v) {index=i;break;} for(int i=0;i<index;i++){ subpre_l.push_back(preorder[i+1]); subin_l.push_back(inorder[i]); } for(int i=index+1;i<preorder.size();i++){ subpre_r.push_back(preorder[i]); subin_r.push_back(inorder[i]); } //递归表达式 TreeNode *root=new TreeNode(v); root->left=buildTree(subpre_l,subin_l); root->right=buildTree(subpre_r,subin_r); return root; } };
方法二:time O(n) space O(1)