杨辉三角 / 二叉树的最大深度
杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
提示:
1 <= numRows <= 30
解题思路
利用上一行的元素计算当前行，遵循杨辉三角的递推关系：
每行的第一个和最后一个元素是 1
其他元素 = 上一行左上方元素 + 上一行正上方元素
代码逻辑
外层循环：控制行数
for (int i = 1; i <= numRows; i++) {
// i 表示当前是第几行
// 第 i 行有 i 个元素
}内层循环：构建当前行
for (int j = 0; j < i; j++) {
// j 表示当前行中的位置索引（从0开始）
}元素计算逻辑
if (j == 0) {
dd.add(1); // 每行第一个元素是1
} else if (j == i - 1) {
dd.add(1); // 每行最后一个元素是1
} else {
// 中间元素 = 上一行的(j-1)位置元素 + 上一行的j位置元素
List<Integer> upp = list.get(list.size() - 1);
dd.add(upp.get(j - 1) + upp.get(j));
}完整代码
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> list = new ArrayList<>();
for (int i = 1; i <= numRows; i++) {
List<Integer> dd = new ArrayList<>();
for (int j = 0; j < i; j++) {
if (j == 0) {
dd.add(1);
} else if (j == i - 1) {
dd.add(1);
} else {
List<Integer> upp = list.get(list.size() - 1);
dd.add(upp.get(j - 1) + upp.get(j));
}
}
list.add(dd);
}
return list;
}
public static void main(String[] args) {
Solution solution = new Solution();
List<List<Integer>> generate = solution.generate(1);
System.out.println(generate);
}
}二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
提示：
树中节点的数量在
[0, 104]区间内。-100 <= Node.val <= 100
解题思路
递归遍历左右子树
这段代码是一个求二叉树最大深度的递归实现，我们按执行逻辑梳理一下：
递归结束条件（base case）
if (root == null) { return 0; }当当前节点为空，说明走到树的尽头（叶子节点的子节点），深度为 0
这是递归的出口，避免无限递归。
递归计算左子树深度
int left = maxDepth(root.left);对
root.left递归调用maxDepth直到走到空节点，才返回 0，然后逐层往上计算深度。
递归计算右子树深度
int right = maxDepth(root.right);同理，对右子树递归计算最大深度。
当前节点深度计算
return Math.max(left, right) + 1;左右子树深度取最大值
再加上当前节点本身的这一层深度（
+1）逐层返回给上一级调用。
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
}广度遍历二叉树
采用广度优先搜索(BFS)的方法。下面是逐步逻辑分析：
基本情况处理
逻辑说明：如果根节点为空，说明树不存在，深度为 0。
if (root == null) {
return 0;
}BFS 初始化
变量说明：
level：记录当前深度，初始为 0。queue：创建一个队列，并将根节点加入队列，作为遍历的起点。
int level = 0;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);BFS 主循环
外层循环：当队列不为空时，说明还有节点需要处理，循环继续。
内层循环：
目标：处理当前层的每一个节点。
步骤：
从队列中取出一个节点。
将其非空的左、右子节点加入队列末尾。
计数器
size减 1，表示已处理完当前层的一个节点。
当
size减至 0 时，表示当前层所有节点已处理完毕。
while (!queue.isEmpty()) { // 外层循环
int size = queue.size(); // 获取当前层的节点数量
while (size > 0) { // 内层循环：处理当前层的所有节点
TreeNode poll = queue.poll(); // 取出队首节点
// 将该节点的子节点加入队列，作为下一层待处理的节点
if (poll.left != null) {
queue.add(poll.left);
}
if (poll.right != null) {
queue.add(poll.right);
}
size--; // 当前层节点计数器减 1
}
level++; // 完成一层处理后，深度加 1
}返回结果
逻辑说明：当队列为空时，表示所有节点都已处理完毕，返回累计的深度
level，即为树的最大深度。
return level;这种方法通过层级遍历的方式，每处理完一层深度加1，最终得到的level就是树的最大深度。
完整代码
class Solution {
public int maxDepth(TreeNode root) {
// 1. 基本情况处理
if (root == null) {
return 0;
}
// 2. BFS 初始化
int level = 0;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
// 3. BFS 主循环
while (!queue.isEmpty()) {
int size = queue.size(); // 获取当前层的节点数量
// 处理当前层的所有节点
while (size > 0) {
TreeNode currentNode = queue.poll(); // 取出队首节点
// 将该节点的子节点加入队列，作为下一层待处理的节点
if (currentNode.left != null) {
queue.add(currentNode.left);
}
if (currentNode.right != null) {
queue.add(currentNode.right);
}
size--; // 当前层节点计数器减1
}
level++; // 完成一层处理后，深度加1
}
// 4. 返回结果
return level;
}
}