leetcode 105从前序与中序遍历序列构造二叉树

leetcode 105从前序与中序遍历序列构造二叉树

 

方法一:直接使用复制的数据递归: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)

 

上一篇:SRP(单一职责)——没有一只能飞能走的鸟


下一篇:java进阶之-Maven,svn,git,maven合拼多个项目