算法 3.1 二叉树+BFS+DFS：二叉树的最大深度

题目描述

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

数据结构

二叉树

算法思维

深度优先遍历 DFS
广度优先遍历 BFS

关键知识点：树

树(tree)是 n(n>0) 个结点(node)的有限集 T，其中：
有且仅有一个特定的结点，称为根(root)
当n>1时，其余结点可分为m(m>0)个互不相交的有限集，每个集合本身是一棵树，称为根的子树(subtree)

树的性质：
1）结点(node)：树的元素，包括数据项+若干指向其子树的分支
2）结点的度(degree)：结点拥有的子树的数目
3）叶子(leaf)：度为0的结点
4）结点的层次(level)：从根结点算起，根为第一层，其孩子为第二层 ……
二叉树的定义：
二叉树是n(n>=0)个结点的有限集，它或为空树，或由两棵分别称为左子树和右子树的互不相交的二叉树构成
二叉树的性质:
1）每个结点最多有两棵子树
2）二叉树的左右子树次序不能颠倒

二叉树的代码实现：

// 定义一棵二叉树
public class TreeNode {
  // 定义节点的值
  int val;
  // 定义左子树
  TreeNode left;
  // 定义右子树
  TreeNode right;
  // 定义初始化方法
  TreeNode(int x) { val = x; } 
}

关键知识点：DFS + BFS

在遍历树的时候，总是从一个结点出发，遍历其子结点。在上图遍历到结点2后，有两种遍历选择：
1）先遍历下一层结点（结点4）及后面所有层直至不能往下再回退
2）先回退将根结点剩余子结点（结点3）遍历完后再遍历下一层结点
第一种遍历方式称为DFS(深度优先遍历)，第二种遍历方式称为BFS(广度优先遍历)

解题步骤

一. Comprehend 理解题意

题目主干

二叉树最大深度：该二叉树所有深度的最大值

二. Choose 选择数据结构与算法

数据结构选择

二叉树

算法思维选择

方案一：广度优先遍历

广度优先遍历所有结点，找出最大深度
数据结构：树，队列
算法思维：广度优先

方案二：深度优先遍历（优化解法）

深度优先遍历所有结点，找出最大深度
数据结构：树
算法思维：深度优先

三. Code 编码实现基本解法

解法一（BFS）思路剖析

是否需要处理边界问题？
• 处理树为空的情况
在遍历根结点（结点1）时如何记录其下一层节点（结点2，结点3）？
• 遍历当前结点时，将其左右子结点加入队列
如何确定某一层结点已被遍历完？
• 在更新目标值后，队列中的结点就是下一层的全部结点，记录此时队列的大小
在BFS过程中如何更新我们的目标值（二叉树最大深度）？
• 遍历完一层结点后，目标值+1

代码实现【重点】

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {return 0;} // 考虑树为空的特殊情况 BFS无法自动处理
        Queue<TreeNode> queue = new LinkedList<TreeNode>();// 使用队列来记录各层节点
        queue.offer(root);// 根节点入队
        int res = 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);// 右子树入队列
                }
                size--; 
            }
            res++;// 新一层节点遍历完成，目标值 + 1
        } 
        return res;
    }
}

时间复杂度：O(n)
• 遍历二叉树，每个结点都会被遍历一次 O(n)

空间复杂度：O(n)
• 取决于队列需要存储的元素数量，最差可以达到 O(n)

执行耗时：1 ms，击败了 17.26% 的Java用户
内存消耗：38.4 MB，击败了 68.25% 的Java用户

四. Consider 思考更优解

解法二（DFS）思路剖析

使用递归的方法遍历二叉树

五. Code 编码实现最优解

class Solution {
    public int maxDepth(TreeNode root) {
        /*
         * DFS:深度优先遍历（递归）
         * */
        //结束条件：当前节点为空
        if (root == null) return 0;

        //递归公式：计算左右子树高度
        int leftMaxDepth = maxDepth(root.left);
        int rightMaxDepth = maxDepth(root.right);

        //主体逻辑:当前层高度 = 左右子树高度最大值 + 1
        return Math.max(leftMaxDepth, rightMaxDepth) + 1;
    }
}