Share my accepted iterative C++ solution with queue


  • 0
    G
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() <= 0) return NULL;
        TreeNode* root = new TreeNode(nums[0]);
        if (nums.size() == 1) return root;
        
        queue<TreeNode*> q;
        queue<int> qS; // starting index
        queue<int> qE; // ending index
        q.push(root);
        qS.push(0); qE.push(nums.size() - 1);
        while (!q.empty())
        {
            TreeNode* n = q.front(); q.pop();
            int start = qS.front(); qS.pop();
            int end = qE.front(); qE.pop();
            int mid = (start + end) / 2;
            n->val = nums[mid];
            int ls = start, le = mid - 1;
            if (ls <= le)
            {
                n->left = new TreeNode(0);
                q.push(n->left);
                qS.push(ls); qE.push(le);
            }
            int rs = mid + 1, re = end;
            if (rs <= re)
            {
                n->right = new TreeNode(0);
                q.push(n->right);
                qS.push(rs); qE.push(re);
            }
        }
        return root;
    }

Log in to reply
 

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