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


  • 0
    A

    Basically the same idea as in Problem 104: Maximum Depth of Binary Tree.
    Time complexity O(n); Space complexity O(1).

    class Solution {
    public:
        int minDepth(TreeNode* root) {
            if (!root) return 0;
            uint m = UINT_MAX, 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;
                        if (!p->left) m = min(m, n-1);
                        n -= d;
                    } else {
                        p->right = t;
                        t = t->left;
                        n++;
                    }
                } else {
                    t = t->right;
                    if (!t) m = min(m, n);
                    n++;
                }
            }
            return m;
        }
    };
    

Log in to reply
 

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