题目链接：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.

这道题的要求是计算二叉树的最大深度。

  1. 深度优先搜索

递归思路，如果当前节点为NULL，返回0；否则返回左右子树的最大深度加1即可。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7

class Solution {
public:
    int maxDepth(TreeNode *root)
    {
        return root == NULL ? 0 : max(maxDepth(root -> left), maxDepth(root -> right)) + 1;
    }
};

  1. 广度优先搜索

思路和Binary Tree Level Order Traversal差不多，只不过这里要求返回的最大深度就是Binary Tree Level Order Traversal的最后vector的长度。因此只需要统计遍历的层数即可。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution
{
public:
    int maxDepth(TreeNode *root)
    {
        if(root == NULL)
            return 0;
        
        int res = 0;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty())
        {
            ++ res;
            for(int i = 0, n = q.size(); i < n; ++ i)
            {
                TreeNode *p = q.front();
                q.pop();
                
                if(p -> left != NULL)
                    q.push(p -> left);
                if(p -> right != NULL)
                    q.push(p -> right);
            }
        }
        
        return res;
    }
};