104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

// Recursion
int maxDepth(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

// Recursion
int maxDepth(TreeNode* root) { // time: O(n); space: O(n)
    int res = -1, cur = 0;
    helper(root, cur, res);
    return res == -1 ? 0 : res;
}
void helper(TreeNode* root, int cur, int& res) {
    if (!root) return;
    ++cur;
    if (!root->left && !root->right) {
        // cout << "root node: " << root->val << endl;
        // cout << "res: " << res << ", cur: " << cur << endl;
        res = max(res, cur);
        // cout << "after update, res: " << res << endl;
    }
    helper(root->left, cur, res);
    helper(root->right, cur, res);
}

// Iteration
int maxDepth(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int res = 0;
    while (!q.empty()) {
        ++res;
        int n = q.size();
        for (int i = 0; i < n; ++i) {
            TreeNode* cur = q.front(); q.pop();
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
    return res;
}