104.力扣（leetcode）二叉树的最大深度（JAVA）

一、目标

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

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

二、代码分析

总代码：

/**
 * 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) {
        Queue<TreeNode> que = new LinkedList<>();
        int depth = 0;
        que.add(root);
        //防止直接传入空节点报异常
        if(root == null){
            return depth;
        }
        while(!que.isEmpty()){
        //记录每一层的节点数，按照节点遍历每个节点单独操作
            int len = que.size();
            while(len != 0){
                TreeNode temp = que.poll();
                if(temp.left != null){
                    que.add(temp.left);
                }
                if(temp.right != null){
                    que.add(temp.right);
                }
                len--;
            }
        //每次遍历完一层的节点就记录一次深度值
            depth++;
        }   
        return depth;
    }
}

  力扣上关于二叉树的定义已经给出，可以直接使用。

  本文选择使用二叉树的层序遍历法解决二叉树最大深度求解问题，思路如下：

  首先进行遍历前的准备，使用一个双端队列来存储遍历到的节点，方便后续操作，开始先先将根节点传入。

        Queue<TreeNode> que = new LinkedList<>();
        int depth = 0;
        que.add(root);
        //防止直接传入空节点报异常
        if(root == null){
            return depth;
        }

  将每层的节点数在遍历之前先储存起来，按照节点数分别从队列中调用poll（）方法取出上一层遍历中储存的顺序节点数，每遍历完一层之后记录一次深度值，依次遍历，直到队列为空（上一层的每个节点均没有子节点），结束。

        while(!que.isEmpty()){
        //记录每一层的节点数，按照节点遍历每个节点单独操作
            int len = que.size();
            while(len != 0){
                TreeNode temp = que.poll();
                if(temp.left != null){
                    que.add(temp.left);
                }
                if(temp.right != null){
                    que.add(temp.right);
                }
                len--;
            }
        //每次遍历完一层的节点就记录一次深度值
            depth++;
        }   

三、总结

  本题就是传统遍历基础上修改而成，不同点在于：
  1. 无需创建LIst对象储存每个节点的值，因为我们要返回的是深度值