104-二叉树的最大深度

Doublew2w大约 2 分钟

给定一个二叉树 root ，返回其最大深度。

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

示例 1：

  输入： root = [3,9,20, null, null,15,7]
 输出： 3

示例 2：

  输入： root = [1, null,2]
 输出： 2

提示：

树中节点的数量在 [0, 10 ⁴] 区间内。
-100 <= Node.val <= 100

前置知识

深度概念
二叉树
DFS、BFS

思路 1: DFS

二叉树的最大深度 = Math.max(左子树的最大深度，右子树的最大深度) + 1

递归三要素:

终止条件： 当 root 为空时，说明不是叶节点，因此深度是 0
单层递归逻辑：计算节点 root 的左子树的深度，计算节点 root 的右子树的深度
返回值：：返回树的深度

关键点

二叉树的最大深度 = Math.max(左子树的最大深度，右子树的最大深度) + 1

代码

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        // 单层递归逻辑：求树的大深度
        // 树的最大深度 = max(左子树的最大深度 ，右子树的最大深度) + 1
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

复杂度分析

令 n 为二叉树节点个数。

时间复杂度： $O(n)$ ，计算树的深度需要遍历所有节点。
空间复杂度： $O(n)$ ，最差情况下（当树退化为链表时），递归深度可达到 N 。

思路 2：BFS

树的层序遍历 / 广度优先搜索往往利用队列实现。

关键点： 每遍历一层，则计数器 +1 ，直到遍历完成，则可得到树的深度。

代码

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
        int res = 0;
        while (!queue.isEmpty()) {
            tmp = new LinkedList<>();
            for(TreeNode node : queue) {
                if (node.left != null) tmp.add(node.left);
                if (node.right != null) tmp.add(node.right);
            }
            queue = tmp;
            res++;
        }
        return res;
    }
}