O(n) time O(1) space Morris In-Order Traversal solution


  • 0
    R
    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if (head == nullptr)
                return nullptr;
                
            int max = 0;
            for (ListNode *p = head; p != nullptr; p = p->next)
                max++;
                
            TreeNode* root = new TreeNode(1);
    
            ListNode* lp = head;
            TreeNode* cur = root;
            while (cur) {
                int curleft = (cur->val) * 2;
                if (curleft > max) { //cur->left == null, output current node, then go to right branch
                    cur->val = lp->val;
                    lp = lp->next;
                    cur = cur->right;
                }
                else {
                    if (cur->left == nullptr){
                        cur->left = new TreeNode(curleft); 
                    }
                    TreeNode* prev = cur->left;
                    int prevright = (prev->val) * 2 + 1;
                    while (prev->right != cur && ((prev->right != nullptr)||(prevright <= max))/*prev->right != nullptr*/) {
                        if (prev->right == nullptr){
                            prev->right = new TreeNode(prevright);
                        }
                        prev = prev->right;
                        prevright = (prev->val) * 2 + 1;
                    }
                    if (prev->right != cur) {//prev->right == nullptr
                        prev->right = cur;
                        cur = cur->left;
                    }
                    else {
                        //output current node
                        int curright = (cur->val) * 2 + 1;
                        cur->val = lp->val;
                        lp = lp->next;
                        prev->right = nullptr;
                        if (curright <= max){
                            if (cur->right == nullptr) {
                                cur->right = new TreeNode(curright);
                            }
                        }
                        cur = cur->right;
                    }
                }
            }
                
            return root;
        }
    };

Log in to reply
 

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