C++ 40ms, solved recursively


  • 0
    A

    递归实现。

    1. 先找到根节点

    2. 分别找到:左子树的前序遍历和中序遍历,右子树的前序遍历和中序遍历

    3. 分别对“左子树的前序遍历和中序遍历”和“右子树的前序遍历和中序遍历”递归调用buidTree函数(private)
      得到左子树和右子树的根节点

    4. 将根节点与左子树和右子树连起来

      class Solution
      {
      public:
      TreeNode buildTree(vector<int> &preorder, vector<int> &inorder)
      {
      int preSize = preorder.size();
      int inSize = inorder.size();
      /

      if(preSize!=inSize)
      throw;
      if(preSize==0)
      return NULL;

           if(preSize!=inSize)
               throw;
           */
           TreeNode *root = buildTree(preorder,0,preSize,inorder,0,inSize);
      
       }
      

      private:
      TreeNode *buildTree(vector<int> &preorder,int preorderL,int preorderR,
      vector<int> &inorder, int inorderL,int inorderR)
      {
      //base line
      int preSize = preorderR-preorderL;
      int inSize = inorderR-inorderL;
      if(preSize!=inSize)
      throw;
      if(preSize==0)
      return NULL;

           int root_val = preorder[preorderL];
           TreeNode *root = new TreeNode(root_val);
      
           if(preSize==1)
               return root;
           
           //利用根节点的数值找出左子树和右子树的范围
           int index = 0;
           for(;inorder[index+inorderL]!=root_val && index+inorderL<inorderR;++index)
           {}
           if(index>=inorderR)
               throw;
      
           //左子树前序遍历和中序遍历的范围
           int leftSubtreePreorderL = preorderL+1;
           int leftSubtreePreorderR = preorderL+index+1;
           int leftSubtreeInorderL = inorderL;
           int leftSubtreeInorderR = inorderL + index;
      
            //右子树前序遍历和中序遍历的范围
            int rightSubtreePreorderL = preorderL+index+1;
            int rightSubtreePreorderR = preorderR;
            int rightSubtreeInorderL = inorderL+index+1;
            int rightSubtreeInorderR = inorderR;
    
    
            //递归调用
            TreeNode *leftSubtree = buildTree(preorder,leftSubtreePreorderL,leftSubtreePreorderR,
                                          inorder,leftSubtreeInorderL,leftSubtreeInorderR);
            TreeNode *rightSubtree = buildTree(preorder,rightSubtreePreorderL,rightSubtreePreorderR,
                                           inorder,rightSubtreeInorderL,rightSubtreeInorderR);
    
            root->left = leftSubtree;
            root->right = rightSubtree;
    
            return root;
        }
    };

  • 0
    X
    struct TreeNode *buildTree(int *preorder, int *inorder, int n) {
        if(n == 0)
            return NULL;
        
        struct TreeNode *root = malloc(sizeof(struct TreeNode));
        root->val = preorder[0];
        
        int rootIndex;
        for(rootIndex=0; inorder[rootIndex] != root->val; ++rootIndex);
        
        root->left = rootIndex == 0 ? NULL : buildTree(preorder+1, inorder, rootIndex);
        
        root->right = rootIndex == n-1 ? NULL : buildTree(preorder+rootIndex+1, inorder+rootIndex+1, n-rootIndex-1);
        
        return root;
    }

  • 0
    A

    Your code is more succinct. You must be more familiar with c/c++ than I.


  • 0
    X

    递归不用这么麻烦吧............


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.