104.二叉树的最大深度——二叉树专题复习

深度优先搜索（DFS）是一种常用的递归算法，用于解决树形结构的问题。在计算二叉树的最大深度时，DFS方法会从根节点开始，递归地计算左右子树的最大深度，然后在返回时更新当前节点所在路径的最大深度。

如果我们知道了左子树和右子树的最大深度 left 和 right，那么该二叉树的最大深度即为 max(left ,right)+1

递归实现：

/**
 * 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 Solution {
    // 定义一个方法，递归地计算二叉树的最大深度
    public int maxDepth(TreeNode root) {
        // 如果根节点为空，则返回0，树的高度为0
        if(root == null) return 0;

        // 递归地计算左子树的最大深度
        int left = maxDepth(root.left);
        // 递归地计算右子树的最大深度
        int right = maxDepth(root.right);
        
        // 返回左子树和右子树中的最大深度，加上当前节点的高度1
        return Math.max(left,right)+1;
    }
}

二叉树的最大深度可以使用广度优先搜索（BFS）来求解，而且可以通过修改BFS的方式来实现。这种方法与之前提到的BFS方法的区别在于，它是逐层地遍历二叉树，而不是逐个节点地遍历。

迭代实现

class Solution {
    // 定义一个队列，用于广度优先搜索（BFS）
    Queue<TreeNode> que = new LinkedList<>();

    public int maxDepth(TreeNode root) {
        // 如果根节点为空，则返回0，树的高度为0
        if(root == null) return 0;

        // 将根节点加入队列
        que.offer(root);
        // 初始化结果变量为0，用于记录最大深度
        int res = 0;

        // 当队列不为空时，执行循环
        while(!que.isEmpty()){
            // 获取队列的当前大小，用于下面的循环控制
            int size = que.size();
            // 当队列中还有节点时，执行循环
            while(size > 0){
                // 从队列中取出一个节点
                TreeNode node = que.poll();
                // 如果当前节点的左子节点不为空，将其加入队列
                if(node.left != null){
                    que.offer(node.left);
                }
                // 如果当前节点的右子节点不为空，将其加入队列
                if(node.right != null){
                    que.offer(node.right);
                }
                // 队列大小减1，因为已经取出了一个节点
                size--;
            }
            // 结果变量加1，表示高度增加了
            res++;
        }
        // 返回计算出的最大深度
        return res;
    }
}