0104. Maximum Depth of Binary Tree.md

Trees

Time Complexity: The time complexity of this code is O(n), where n is the number of nodes in the binary tree. This is because the code recursively visits each node in the binary tree exactly once, and performs a constant amount of work at each node.

Space Complexity: The space complexity of this code is O(h), where h is the height of the binary tree. This is because the code uses a recursive algorithm to traverse the binary tree, and the maximum depth of the recursive call stack is equal to the height of the tree. Therefore, in the worst case, the space required by the call stack is proportional to the height of the tree.

Recusive

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return 1 + max(left, right);
    }
};

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return null;
    let leftDepth = maxDepth(root.left);
    let rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
};

Itetative

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;

        queue<TreeNode*> q;
        q.push(root);
        int depth = 0;

        while (!q.empty()) {
            int count = q.size();   // 当前层节点数
            depth++;

            for (int i = 0; i < count; i++) {
                TreeNode* cur = q.front();
                q.pop();

                if (cur->left)  q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
        }

        return depth;
    }
};