104. 二叉树的最大深度

Posted on Edited on In , ,
转载自Leet Code

题目描述

给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

      3      /   \     9     20           /            15   7

返回它的最大深度 3 。

我的代码: DFS

\(T(N) = O(N)\), \(S(Height) = O(Height)\)

{.line-numbers}
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class MySolution104 // DFS
{
    public int maxDepth(TreeNode root) 
    {
    	if (root==null) return 0;
    	else if (root.left==null&&root.right==null) return 1;
    	
    	else return 1+Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

方法：BFS

\(T(N) = O(N)\), \(S(N) = O(N)\)

此时BFS队列中存放的是「当前层的所有节点」。 每拓展到下一层，只从队列里拿出一个节点， 需要将队列里的所有节点都拿出来拓展， 保证每次拓展完的时候队列里存放的都是当前层的所有节点， 最后用一个变量 \(ans\) 来维护拓展次数， 二叉树的最大深度就是 \(ans\)。

{.line-numbers}
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
class Solution104
{
    public int maxDepth(TreeNode root) 
    {
    	if (root==null) return 0;
    	
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        int ans = 0;
        
        while (!queue.isEmpty())
        {
        	int size = queue.size();
        	while (size>0)
        	{
        		TreeNode node = queue.poll();
        		if (node.left!=null) queue.add(node.left);
        		if (node.right!=null) queue.add(node.right);
        		size--;
        	}
        	ans++;
        }
        
        return ans;
    }
}