C++ O(1) space cost without any changing using Prev Pointer


  • 0
    F
    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            if (!root)  return 0;
            stack<TreeNode*> s;
            s.push(root);
            int maxDepth = 0;
            TreeNode* prev = nullptr;
            while (!s.empty()) {
                TreeNode* cur = s.top();
                if (!prev || prev->left == cur || prev->right == cur) {
                    if (cur->left) {
                        s.push(cur->left);
                    }
                    else if (cur->right) {
                        s.push(cur->right);
                    }
                } else if (prev == cur->left) {
                    if (cur->right) {
                        s.push(cur->right);
                    }
                } else { //the root node whose all the sub-tree node have been traversed
                    s.pop();
                }
                prev = cur;
                if (s.size() > maxDepth)
                    maxDepth = s.size();
            }
            return maxDepth;
        }
    };

Log in to reply
 

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