题目描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

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

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

     3
    / \
   9  20
     /  \
    15   7
 返回它的最大深度 3 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1 – DFS

这是道经典的BinaryTree的模版题，我们声明函数private int helper(TreeNode node, int depth) ，当node是叶子结点时返回depth，如果node的左子树非空则递归调用helper(node.left, depth+1)；当node的右子树非空，则递归调用helper(node.right, depth+1); 当node为空，则返回0。

时间复杂度O(n)，空间复杂度O(n)。全部代码如下：

class Solution {
    public int maxDepth(TreeNode root) {
        return helper(root, 1);
    }

    private int helper(TreeNode node, int depth) {
        if (node == null)
            return 0;
        
        if (node.left == null && node.right == null)
            return depth;

        int maxDepth = helper(node.left, depth + 1);

        maxDepth = Math.max(maxDepth, helper(node.right, depth + 1));

        return maxDepth;
    }
}

解法2 – BFS

当然这道题也可以用BFS来做，我们需要一个队列，还有一个Map<TreeNode, Integer>用来存放节点对应的深度。如果node的左子树非空，就将它如队列，然后depth+1放入map中；右子树同理。然后还需要一个存放答案的变量ans，如果取出节点的深度大于ans就更新它，最后返回ans。

复杂度和解法1相同，但因为用到了Map导致overhead比较大，实际运行时间比解法1慢很多。全部代码如下：

class Solution {
    public int maxDepth(TreeNode root) {
        int ans = 0;
        if (root == null)
            return ans;

        Queue<TreeNode> queue = new LinkedList<>();
        Map<TreeNode, Integer> nodeDepth = new HashMap<>();

        queue.offer(root);
        nodeDepth.put(root, 1);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int depth = nodeDepth.get(node);

            ans = Math.max(ans, depth);

            if (node.right != null) {
                queue.offer(node.right);
                nodeDepth.put(node.right, depth + 1);
            }

            if (node.left != null) {
                queue.offer(node.left);
                nodeDepth.put(node.left, depth + 1);
            }
        }

        return ans;
    }
}