Easy understanding c++ O(n) time, O(1) space.


  • 2
    X

    Too many post to dig out if anyone has same idea.

    Three step. each step is O(n) time.

    1. Get the number of nodes.

    2. make a balanced tree. (pre-order, bfs)

    3. assign values. (in-order, dfs)

    codes:

        TreeNode* sortedListToBST(ListNode* head) {
            if (head == NULL) return NULL;
            // get list size
            int n = 0;
            ListNode *scan = head;
            while (scan) {
                n++; scan = scan->next;
            }
            // make balance tree
            TreeNode * root = makeTree(n);
            //assign values
            inorder(root, head);
            return root;
        }
        ListNode * inorder(TreeNode *root, ListNode * node) {
            if (root->left != NULL) node = inorder(root->left, node);
            root->val = node->val;
            node = node->next;
            if (root->right != NULL) node = inorder(root->right, node);
            return node;
        }
        
        TreeNode* makeTree(int n) {
            TreeNode * root = new TreeNode(0);
            queue<TreeNode *> q;
            q.push(root);
            n--;
            while (true) {
                if (n == 0) break;
                TreeNode *x = q.front();
                q.pop();
                x->left = new TreeNode(0);
                q.push(x->left);
                n--;
                if (n == 0) break;
                x->right = new TreeNode(0);
                q.push(x->right);
                n--;
                if (n == 0) break;
            }
            return root;
        }

  • 0
    C

    step2 make a balanced tree, means o(n) space not o(1), although I agree it is a must.


Log in to reply
 

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