C++ O(n) time O(1) space solution using Morris traversal


  • 2
    A

    This solution use a inorder Morris traversal. We need to keep track of the depth in addition to the standard traversal. The max depth only need to updated before the depth is reduced. Note that BFS and DFS uses O(log n) space.

    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            if (root == nullptr) {
                return false;
            }
            int ret = 0;
            int depth = 0;
            auto cur = root;
            while (cur) {
                if (!cur->left) {
                    cur = cur->right;
                    ++depth;
                }
                else {
                    auto prev = cur->left;
                    int dist = 1;
                    while (prev->right && prev->right != cur) {
                        prev = prev->right;
                        ++dist;
                    }
                    if (prev->right) {
                        prev->right = nullptr;
                        cur = cur->right;
                        ret = max(ret, depth);
                        depth -= dist;
                    }
                    else {
                        prev->right = cur;
                        cur = cur->left;
                        ++depth;
                    }
                }
            }
            return max(ret, depth);
        }
    };

Log in to reply
 

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