C++ Non-recursive O(1) space solution, inspired by Morris Traversal


  • 0
    A

    Morris, god of BST.

    class Solution {
    public:
        void flatten(TreeNode* root) {
            TreeNode *p, *t = root;
            while (t) {
                if ((p = t->left) && t->right) {
                    while (p->right) p = p->right;
                    p->right = t->right;
                }
                if (t->left) t->right = t->left, t->left = NULL;
                t = t->right;
            }
        }
    };
    

    Here is the trivial stack version O(n) space solution for reference

    class Solution {
    public:
        void flatten(TreeNode* root) {
            if (!root) return;
            TreeNode *t;
            stack<TreeNode*> k;
            k.push(root);
            while (!k.empty()) {
                t = k.top();
                k.pop();
                if (t->right) k.push(t->right);
                if (t->left) k.push(t->left);
                t->left = NULL;
                t->right = k.empty() ? NULL : k.top();
            }
        }
    };
    

Log in to reply
 

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