题目描述
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点最长路径上的节点数
说明：叶子节点是指没有子节点的节点
数据结构
- 二叉树
算法思维
- 深度优先遍历 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;
}
}
时间复杂度：O(n)
• 遍历二叉树，每个结点都会被遍历一次 O(n)
空间复杂度：O(h)
• h 是二叉树的高度
• 递归需要栈，而栈的深度取决于二叉树的高度
执行耗时：0 ms，击败了 100.00% 的Java用户
内存消耗：38.5 MB，击败了 44.65% 的Java用户
六. Change 变形与延伸
题目变形
- （练习）二叉树的层次遍历（Leetcode 104）
延伸扩展
- 在树的问题中使用DFS（递归）往往可以使复杂问题迎刃而解
- 树这种数据结构在数据库中有广泛的作用，可以提高查询速度
- 面试考察中重点考察的数据结构
网友评论