Yet another iterative solution C++ O(n)


  • 0
    D
     struct Data
     {
         TreeNode *node;
         int l;
         int r;
         Data(int iL, int iR, vector<int> &num)
         {
             l = iL;
             r = iR;
             node = NULL;
             
             if (l>=r) return ;
             
             int mid = l + (r-l)/2;
             node = new TreeNode(num[mid]);
         }
     };
     
    class Solution {
    public:
        
        TreeNode *sortedArrayToBST(vector<int> &num) {
            stack<Data> s;
            
            Data root(0, num.size(), num);
            s.push(root);
            
            while (!s.empty()) 
            {
                Data pop = s.top(); s.pop();
            
                if (!pop.node) continue;
                
                int mid = pop.l + (pop.r - pop.l)/2;
                
                Data left(pop.l, mid, num);
                Data right(mid+1, pop.r, num);
                
                pop.node->left = left.node;
                pop.node->right = right.node;
                
                s.push(left);
                s.push(right);
            }
            
            return root.node;
        }
    };

  • 0
    I

    A slight modification on this approach

     struct Node{
         TreeNode* t;
         int l;
         int r;
         Node(vector<int> &num, int l, int r){
             this->t = new TreeNode(num[l+(r-l)/2]);
             this->l = l;
             this->r = r;
         }
         
         Node* getLeft(vector<int> &num){
             int m = l + (r-l)/2;
             if(l>=m) return NULL;
             Node* left = new Node(num, l, m);
             t->left = left->t;
             return left;
         }
         
         Node* getRight(vector<int> &num){
             int m = l + (r-l)/2;
             if(m+1>=r) return NULL;
             Node* right = new Node(num, m+1, r);
             t->right = right->t;
             return right;
         }
     };
     
    class Solution {
    public:
    
        TreeNode *sortedArrayToBST(vector<int> &num) {
            if(num.size()==0) return NULL;
            stack<Node*> s;
            Node* root = new Node(num, 0, num.size());
            s.push(root);
            while(!s.empty()){
                Node* n = s.top(); s.pop();
                
                Node* left = n->getLeft(num);
                if(left) s.push(left);
                
                Node* right = n->getRight(num);
                if(right) s.push(right);
            }
            return root->t;
        }
    };

  • 0
    D

    Similar approach in Java

    public class Solution {
        public TreeNode sortedArrayToBST(int[] num) {
            if(num.length == 0) return null;
            
            Stack<ArrayNode> stack = new Stack<ArrayNode>();
            int middle ;
            ArrayNode aroot = new ArrayNode(num, 0, num.length-1);
            TreeNode root = aroot.r;
            stack.push(aroot);
            
            while(!stack.empty()){
                ArrayNode n = stack.pop();
                middle = n.left + (n.right-n.left)/2;
                if(n.right > middle) {
                    ArrayNode rightN = new ArrayNode(num, middle+1, n.right);
                    n.r.right = rightN.r;
                    stack.push(rightN);
                }
                if(n.left < middle){
                    ArrayNode leftN = new ArrayNode(num, n.left, middle-1);
                    n.r.left = leftN.r;
                    stack.push(leftN);
                }
            }
            return root;
        }
        
        private class ArrayNode {
            TreeNode r;
            int left;
            int right;
            public ArrayNode(int[] num, int left, int right){
                r = new TreeNode(num[left + (right-left)/2]); //check
                this.left = left;
                this.right = right;
            }
        }
    }

Log in to reply
 

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