C++ Non-recursive O(1) space solution, based on Morris Traversal


  • 0
    A

    Time complexity O(n); Space complexity O(1).
    IMHO, particularly for this problem, recursive solution is meaningless.

    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            if (!root) return 0;
            uint m = 1, n = 1;
            TreeNode *p, *t = root;
            while (t) {
                if (p = t->left) {
                    uint d = 1;
                    while (p->right && p->right != t) { p = p->right; d++; }
                    if (p->right) {
                        p->right = NULL;
                        t = t->right;
                        n -= d;
                    } else {
                        p->right = t;
                        t = t->left;
                        m = max(m, (n++)+d);
                    }
                } else {
                    t = t->right;
                    if (t) n++;
                }
            }
            return max(m, n);
        }
    };
    

Log in to reply
 

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