my Non-Recursive version


  • 0
    C
    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if(! head) return NULL;
            ListNode* tlst = head;
            TreeNode* root = new TreeNode(0);
            tlst = tlst->next; 
            queue<TreeNode*> que;
            que.push(root);
            while(tlst){
                TreeNode *tn = que.front();
                que.pop();
                if(tlst){
                    tn->left = new TreeNode(0);
                    que.push(tn->left);
                    tlst = tlst->next;
                }
                if(tlst){
                    tn->right = new TreeNode(0);
                    que.push(tn->right);
                    tlst = tlst->next;
                }
            }
            
            stack<TreeNode*> stk;
            TreeNode* tp = root;
            tlst = head;
            while(tp || !stk.empty()){
                if(tp){
                    stk.push(tp);
                    tp = tp->left;
                }
                else{
                    tp = stk.top();
                    stk.pop();
                    tp->val = tlst->val;
                    tlst = tlst->next;
                    tp = tp->right;
                }
            }
            return root;
        }
    };

Log in to reply
 

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