题目描述

题干：
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

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

---

题解思路

当时考研王道书上的例题，求最大深度，首先想到的就是左右递归，求出最后最长的子树

这就是典型的深度优先遍历，也是我心里一直记住的办法，本来代码实现也不长，官方题解也是这个办法

但是在评论区一个老哥的一个三目运算符确实写的优雅，所以下面的代码我也借鉴了他的写法

说到深度优先遍历，当然广度优先遍历的方法也可以解决这个问题，但是写完代码之后，我越发觉得这就是层序遍历

---

正确代码

    //深度优先遍历
    public int maxDepth(TreeNode root) {
        return (root == null) ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    //广度优先遍历
    public int maxDepth1(TreeNode root) {
        if (root == null) return 0;
        //用队列存储遍历的元素
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        //ans统计最后遍历完的层数
        int ans = 0;
        //只要队列中有元素，就一直往下一层遍历
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0){
                TreeNode node = queue.poll();
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
                //出队列-1
                size--;
            }
            //每循环完一层，层数+1
            ans++;
        }
        return ans;
    }

---

总结

深度优先遍历没得说，就是以后注意语法的灵活运用，用最简练的代码达到预期的功能

广度优先遍历中用到了泛型，其实我自己对于泛型的理解是不到位的，因为自己在敲代码中很少使用

只知道是为了类型安全和优化性能，并且消除了强制转换的风险，以后真正理解了在做一篇文章解释吧

而且还用到了队列的两种方法，offer()和poll()，其实同时作为添加和删除方法，还是有些区别的

在队列元素为空的情况下，remove() 方法会抛出NoSuchElementException异常，poll() 方法只会返回 null 

在容量已满的情况下，add() 方法会抛出IllegalStateException异常，offer() 方法只会返回 false 

文章如果存在问题或者有更好的题解，希望大佬斧正和评论，各自努力，你我最高处见