Maximum Depth of Binary Tree

Posted on Edited on In Views:

104.Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

img

1
2
Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

1
2
Input: root = [1,null,2]
Output: 2

深度优选搜索：

时间复杂度：O(n)

空间复杂度：O(height)

1
2
3
4
int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

广度优先搜索：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    queue<TreeNode*> Q;
    Q.push(root);
    int ans = 0;
    while (!Q.empty()) {
        int sz = Q.size();
        while (sz > 0) {
            TreeNode* node = Q.front();Q.pop();
            if (node->left) Q.push(node->left);
            if (node->right) Q.push(node->right);
            sz -= 1;
        }
        ans += 1;
    } 
    return ans;
}