题目描述

求给定二叉树的最大深度，

最大深度是指树的根结点到最远叶子结点的最长路径上结点的数量。

方法一： 递归

解题思路

二叉树的问题最常用的方法就是递归，将大规模的问题划成小规模的问题，每个问题的求解方法都是一样的，最后规模小到方便求出答案，再由小规模的问题答案求出大规模的问题答案。

求以根节点为二叉树的最大深度，可以先求出根节点的左子树上的高度是多少，再求出右子树上的高度是多少，这两者的最大高度就是以根节点为二叉树的最大深度。

根节点的左子树，仍然是一棵二叉树，也可以用同样的方法求出它的最大深度。

根节点的右子树，也仍然是一颗二叉树，也可以用同样的方法求出它的最大深度。

以下是以 [1，0，2，8] 为二叉树的 流程演示：

复杂度分析

时间复杂度： O(N)

每个节点都会被递归遍历访问到，一共有 N 个节点， 所以时间复杂度为 O(N)

空间复杂度： O(N)

空间上的开销主要在 递归栈 的存储上，最多的递归栈就是这棵二叉树的高度个，即O(h)，又因为二叉树的高度 h = logN，所以空间复杂度为 O(logN)；
但最坏的情况下，可以把每个节点都压入栈中，即空间复杂度可以达到 O(N)。

代码示例：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 整颗树的根节点所处的高度为 1
        return process(root, 1);
    }

    /**
     * 
     * @param root  树的根节点
     * @param depth 这个根节点所处 的高度
     * @return 以 root 为根节点的树 的高度是多少
     */
    public int process(TreeNode root, int depth) {
        // 当 root 节点不存在， 则高度就是它的父节点所处的高度
        // 否则就是 root 节点本身所处的高度，因为不存在，所以不会是 depth，而是它上一级的高度
        if (root == null) {
            return depth - 1;
        }

        // root 节点的左子树高度
        int leftDepth = process(root.left, depth + 1);
        // root 节点的右子树高度
        int rightDepth = process(root.right, depth + 1);

        // 左右子树较高的那个高度，就是整颗树的高度
        return Math.max(leftDepth, rightDepth);
    }
}

方法二： 层序遍历

解题思路

二叉树的层序遍历可以很自然的求出树的高度，有多少层它的高度就是多少。

实现层序遍历最常用的方法就是借助队列结构，先将一层上的节点装入队列中，然后再从队列中以此拿出来，看看每个节点是否有左右孩子，也就是看看每个节点是否有下一层，如果有，就将下一层的节点再次入队。

需要注意的是每次遍历完一层之后，高度就会增加1，最简单的方法就是需要知道每层有多少个节点，拿出指定个数的节点出来就是遍历完了一层。

具体思路请参见示例代码。

以下是以 [1，0，2，8] 为二叉树的 流程演示：

复杂度分析

时间复杂度： O(N)

每个节点都需要遍历到，总共有 N 个节点，所以时间复杂度为 O(N)

空间复杂度：O(N)

空间上的开销主要是在队列的存储上，最多的时候就是看哪一层的节点个数最多，

极端情况下就是一颗满二叉树，叶子节点那一层是最多的，所以空间复杂度为 O(N)

代码示例

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 层序遍历需要用到的 队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 将个根节点入队
        queue.add(root);
        // 记录高度的信息，初始为 0， 每遍历一层就加 1
        int depth = 0;

        // 当队列不为空时，也就是这一层还有节点
        while (!queue.isEmpty()) {
            // 这一层有多少个节点
            int size = queue.size();
            // 挨个取出这些（这一层）节点
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                // 当前节点有 左节点， 使左节点入队
                if (node.left != null) {
                    queue.add(node.left);
                }
                // 当前节点有 右节点， 使右节点入队
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            // 每遍历一层， 高度就加 1
            depth++;
        }

        // 返回整颗树的高度
        return depth;
    }

}