104.md

104. Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• -100 <= Node.val <= 100

Solution

这道题目我们可以用两种方法

第一种是 bfs 层序遍历，因为深度和层的概念是一致的，很直观。

看一下总共能走多少层就可以了。

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root); // 将根节点加入到队列的首部
        //q.addLast(root);或者加到尾部
        int depth = 0; 
        while (!q.isEmpty()) {
            //每一层开始
            depth++; 
            int size = q.size(); 
            for (int i = 0; i < size; i++) {
                //q.pollFirst(); 
                TreeNode node = q.poll(); // 使用 poll() 方法获取队列中的节点
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
        }
        return depth; 
    }
}

当然我们也可以用 dfs 的方法，每个节点都携带一个深度。 到叶子节点的时候我们就更新深度.

class Solution {
    int depth=0;
    public int maxDepth(TreeNode root) {
         dfs(root,1);
         return depth; 
    }
    void dfs(TreeNode root, int cur_depth){
        if(root == null) return;
        //其实这个判断也可以去掉，可以每个节点都判断一次
        //但是叶子节点可以减少判断的次数
        if(root.left ==null && root.right==null){
            depth = Math.max(depth,cur_depth);
            return;
        }
        dfs(root.left,cur_depth+1);
        dfs(root.right,cur_depth+1);
    }
}