题目
给你二叉树的根节点 root ，返回其节点值的 层序遍历。（即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]示例 2：
输入：root = [1]
输出：[[1]]示例 3：
输入：root = []
输出：[]提示：
- 树中节点数目在范围 [0, 2000] 内
- -1000 <= Node.val <= 1000
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-level-order-traversal
方法一：迭代法
迭代法需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
要注意的是，为什么要控制只弹出 size 个元素，因为队列里的元素数量是不断变化的。如果不提前把 size 记录下来，就不知道要弹出多少个元素
public class T102 {
// 层序遍历，使用队列
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
// queue.add(root);
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> vec = new ArrayList<>();
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
vec.add(node.val);
if (node.left != null) {
// queue.add(node.left);
queue.offer(node.left);
}
if (node.right != null) {
// queue.add(node.right);
queue.offer(node.right);
}
}
result.add(vec);
}
return result;
}
}方法二：递归法
递归法就是深度优先遍历二叉树，把每个结点的值加入到二维列表中。关键是加入到二维列表的哪个位置，由于要实现层序遍历的效果，自然不能是顺序加入到二维列表中。因此需要一个变量 depth 记录深度（也可叫层数），depth 从 0 开始，depth 层结点的值就加入到二维列表中的第 depth 个一维列表。
public class T102 {
// 递归法
// 先序遍历得到的序列依次填到对应层数的数组
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
int depth = 0;
order(root, result, depth);
return result;
}
private void order(TreeNode root, List<List<Integer>> result, int depth) {
if (root == null) {
return;
}
// 若result.size()等于depth，说明该结点为depth层第一个结点
if (result.size() == depth) {
result.add(new ArrayList<>());
}
result.get(depth).add(root.val);
order(root.left, result, depth + 1);
order(root.right, result, depth + 1);
}
// 递归写法二
public List<List<Integer>> levelOrder2(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
dfs(root, result, 0);
return result;
}
private void dfs(TreeNode root, List<List<Integer>> result, int depth) {
if (result.size() == depth) {
result.add(new ArrayList<>());
}
result.get(depth).add(root.val);
if (root.left != null) {
dfs(root.left, result, depth + 1);
}
if (root.right != null) {
dfs(root.right, result, depth + 1);
}
}
}相关题目
1、T107 二叉树的层序遍历Ⅱ
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]示例 2：
输入：root = [1]
输出：[[1]]示例 3：
输入：root = []
输出：[]提示：
- 树中节点数目在范围 [0, 2000] 内
- -1000 <= Node.val <= 1000
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii
思路：
相对于 T102 二叉树的层序遍历，就是最后把 result 列表反转一下就可以了。既可用队列，也可用递归
或者采用 BFS，但在每一层的遍历结果添加进二维列表时，直接采用头插法，这样也能实现反转的效果。用这种方法要注意，此时 result 声明时必须用 LinkedList，接收也必须用 LinkedList，即 LinkedList<List<Integer>> result = new LinkedList<>();，因为头插是 LinkedList 特有的方法
public class T107 {
// 层序遍历，使用队列
public List<List<Integer>> levelOrderBottom(TreeNode root) {
// List<List<Integer>> result = new ArrayList<>();
LinkedList<List<Integer>> result = new LinkedList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> vec = new ArrayList<>();
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
vec.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
// result.add(vec);
result.addFirst(vec); // 加入二维数组时采取头插法
}
// 最后对二维列表进行反转
// Collections.reverse(result);
return result;
}
// 递归法
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
int depth = 0;
order(root,result,depth);
Collections.reverse(result);
return result;
}
private void order(TreeNode root, List<List<Integer>> result, int depth) {
if (root == null) {
return;
}
if (result.size() == depth) {
result.add(new ArrayList<>());
}
result.get(depth).add(root.val);
order(root.left, result, depth + 1);
order(root.right, result, depth + 1);
}
}2、T199 二叉树的右试图
给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1：
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]示例 2：
输入: [1,null,3]
输出: [1,3]示例 3：
输入: []
输出: []提示:
- 二叉树的节点个数的范围是 [0,100]
- -100 <= Node.val <= 100
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-right-side-view
思路：
使用队列层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是就放进 result 数组中，随后返回 result 就可以了。
也可使用递归，由于结果存放在一维列表中，所以列表中下标 depth 处就只能是第 depth 层最右边的值，因此深搜时要不断更新 result 下标 depth 处的值，而且必须先递归左子树，再递归右子树
public class T199 {
// 层序遍历，使用队列
public List<Integer> rightSideView1(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
// 将每一层的最后元素放入result数组中
if (i == (size - 1)) {
result.add(node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return result;
}
// 递归法
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
int depth = 0;
order(root, result, depth);
return result;
}
private void order(TreeNode root, List<Integer> result, int depth) {
if (root == null) {
return;
}
// 使用if...else优化对每层第一个节点的重复操作
if (result.size() == depth) {
result.add(root.val);
} else {
result.set(depth, root.val);
}
order(root.left, result, depth + 1);
order(root.right, result, depth + 1);
}
}3、T637 二叉树的层平均值
给定一个非空二叉树的根节点 root，以数组的形式返回每一层节点的平均值。与实际答案相差 10^-5^ 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。示例 2：
输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]提示：
- 树中节点数量在 [1, 104] 范围内
- -231 <= Node.val <= 231 – 1
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/average-of-levels-in-binary-tree
思路：
使用队列层序遍历的时候把每层求总和再取均值。
或者使用深度优先搜索，都由于深搜时不知道二叉树每层元素的个数，所以需要维护两个数组，counts 用于存储二叉树的每一层的节点数，sums 用于存储二叉树的每一层的节点值之和。搜索过程中需要记录当前节点所在层，如果访问到的节点在第 i 层，则将 counts[i] 的值加 1，并将该节点的值加到 sums[i]。遍历结束之后，第 i 层的平均值即为 sums[i] / counts[i]。
public class T637 {
// 层序遍历，使用队列
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
double sum = 0; // 统计每一层的和
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
sum += node.val;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(sum / size); // 将每一层均值放进结果集
}
return result;
}
// 递归法
public List<Double> averageOfLevels2(TreeNode root) {
List<Double> result = new ArrayList<>();
List<Double> sums = new ArrayList<>();
List<Integer> counts = new ArrayList<>();
dfs(root, 0, counts, sums);
for (int i = 0; i < sums.size(); i++) {
result.add(sums.get(i) / counts.get(i));
}
return result;
}
private void dfs(TreeNode root, int depth, List<Integer> counts, List<Double> sums) {
if (root == null) {
return;
}
if (depth == sums.size()) {
sums.add(1.0 * root.val);
counts.add(1);
} else {
sums.set(depth, sums.get(depth) + root.val);
counts.set(depth, counts.get(depth) + 1);
}
dfs(root.left, depth + 1, counts, sums);
dfs(root.right, depth + 1, counts, sums);
}
}4、T429 N 叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]提示：
- 树的高度不会超过 1000
- 树的节点总数在 [0, 104] 之间
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/
思路：
和前面的题差不多，但这是个 N 叉树，每个根节点的所有孩子节点构成了一个 List，所以在迭代遍历和递归遍历中都只需要再添加一个循环来遍历每个结点的孩子节点集合即可。
public class T429 {
// 层序遍历
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> vec = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
vec.add(node.val);
for (Node child : node.children) {
if (child != null) {
queue.offer(child);
}
}
}
result.add(vec);
}
return result;
}
// 递归法
public List<List<Integer>> levelOrder2(Node root) {
List<List<Integer>> result = new ArrayList<>();
int depth = 0;
dfs(root, result, depth);
return result;
}
private void dfs(Node root, List<List<Integer>> result, int depth) {
if (root == null) {
return;
}
if (result.size() == depth) {
result.add(new ArrayList<>());
}
result.get(depth).add(root.val);
for (Node child : root.children) {
dfs(child, result, depth + 1);
}
}
private class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
}
}5、T515 在每个树行中找最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]示例2：
输入: root = [1,2,3]
输出: [1,3]提示：
- 二叉树的节点个数的范围是 [0,104]
- -231 <= Node.val <= 231 – 1
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row/description/
思路：
把对每个结点的处理换成比较找最大值即可
public class T515 {
// 层序遍历
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
int max = Integer.MIN_VALUE;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.val > max) {
max = node.val;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(max);
}
return result;
}
// 递归法，写法一
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<>();
dfs(root, result, 0);
return result;
}
private void dfs(TreeNode root, List<Integer> result, int depth) {
if (root == null) {
return;
}
if (result.size() == depth) {
result.add(root.val);
}
if (root.val > result.get(depth)) {
result.set(depth, root.val);
}
dfs(root.left, result, depth + 1);
dfs(root.right, result, depth + 1);
}
// 递归法，写法二
public List<Integer> largestValues2(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
dfs(root, result, 0);
return result;
}
private void dfs(TreeNode root, List<Integer> result, int depth) {
if (result.size() == depth) {
result.add(root.val);
}
if (root.val > result.get(depth)) {
result.set(depth, root.val);
}
if (root.left != null) {
dfs(root.left, result, depth + 1);
}
if (root.right != null) {
dfs(root.right, result, depth + 1);
}
}
}6、T116 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例 1：
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。示例 2：
输入：root = []
输出：[]提示：
- 树中节点的数量在 [0, 2^12^ – 1] 范围内
- -1000 <= node.val <= 1000
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/description/
思路：
本题依然是层序遍历，每次单层遍历的时候完成 next 指针填充就可以了。
要填充每个节点的 next 指针，就是要让前一个节点的 next 指向后一个节点，所以需要记录前一个节点。
方法一和方法二的思想其实是一样的，只是节点连接的方式不同。
- 方法一在遍历每一层时，使用
preNode来记录前一个节点，并在每次循环中更新preNode.next。 - 方法二在遍历每一层时，首先处理第一个节点，然后在
for循环中处理剩余节点，并将前一个节点node与当前节点nextNode连接。
方法一的代码结构相对简单，逻辑集中在 for 循环中，通过 preNode 来连接节点。
方法二的代码结构稍微复杂一些，首先处理第一个节点，然后在 for 循环中处理剩余节点。
public class T116 {
// 层序遍历，方法一
public Node connect(Node root) {
if (root == null) {
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
Node preNode = null;
Node node;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
node = queue.poll();
if (i != 0) {
preNode.next = node;
}
preNode = node;
/*if (i == 0) {
preNode = node;
} else {
preNode.next = node;
preNode = node;
}*/
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return root;
}
// 层序遍历，方法二
public Node connect2(Node root) {
if (root == null) {
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
Node node, nextNode;
while (!queue.isEmpty()) {
int size = queue.size();
node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
for (int i = 1; i < size; i++) {
nextNode = queue.poll();
if (nextNode.left != null) {
queue.offer(nextNode.left);
}
if (nextNode.right != null) {
queue.offer(nextNode.right);
}
node.next = nextNode;
node = nextNode;
}
}
return root;
}
private class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
}
}7、T117 填充每个节点的下一个右侧节点指针 Ⅱ
给定一个二叉树：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL。
示例 1：
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。示例 2：
输入：root = []
输出：[]提示：
- 树中的节点数在范围 [0, 6000] 内
- -100 <= Node.val <= 100
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/
思路：
使用层序遍历的话，本题和 T116 填充每个节点的下一个右侧节点指针并无区别
public class T117 {
// 层序遍历，方法一
public Node connect(Node root) {
if (root == null) {
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
Node preNode = null;
Node node;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
node = queue.poll();
if (i != 0) {
preNode.next = node;
}
preNode = node;
/*if (i == 0) {
preNode = node;
} else {
preNode.next = node;
preNode = node;
}*/
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return root;
}
// 层序遍历，方法二
public Node connect2(Node root) {
if (root == null) {
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
Node node, nextNode;
while (!queue.isEmpty()) {
int size = queue.size();
node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
for (int i = 1; i < size; i++) {
nextNode = queue.poll();
if (nextNode.left != null) {
queue.offer(nextNode.left);
}
if (nextNode.right != null) {
queue.offer(nextNode.right);
}
node.next = nextNode;
node = nextNode;
}
}
return root;
}
private class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
}
}8、T104 二叉树的最大深度
给定一个二叉树 root，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3示例 2：
输入：root = [1,null,2]
输出：2提示：
- 树中节点的数量在 [0, 104] 区间内。
- -100 <= Node.val <= 100
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
思路：
方法一：层序遍历。因为最大的深度就是二叉树的层数，所以只需层序遍历记录下遍历的层数即可。
方法二：递归法。需要两个全局变量 result 和 depth。每调用一次 dfs 函数，depth 就应该加 1，代表走到了下一层深度增加一。每当遇到叶子节点，depth 就可能是最大深度，就需要和 result 比较，若比 result 大则更新 result 的值。调用完 dfs 函数别忘了让 depth 减 1，这样才能保证 depth 是当前的深度。
public class T104 {
// 层序遍历
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
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);
}
}
depth++;
}
return depth;
}
// 递归法
private int result = Integer.MIN_VALUE;
private int depth = 0;
public int maxDepth2(TreeNode root) {
if (root == null) {
return 0;
}
dfs(root);
return depth;
}
private void dfs(TreeNode node) {
depth++;
if (node.left == null && node.right == null) {
result = Math.max(result, depth);
return;
}
if (node.left != null) {
dfs(node.left);
depth--;
}
if (node.right != null) {
dfs(node.right);
depth--;
}
}
}9、T111 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5提示：
- 树中节点数的范围在 [0, 105] 内
- -1000 <= Node.val <= 1000
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
思路：
方法一：使用层序遍历，直到遍历到第一个叶子节点，此时该叶子节点所处的层数就是最小深度。
方法二：递归法，和 T104 二叉树的最大深度基本相同，只需把 max 方法改成 min 方法即可。
public class T111 {
// 层序遍历
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int depth = 0;
while (!queue.isEmpty()) {
int size = queue.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return depth;
}
// 递归法
private int result = Integer.MAX_VALUE;
private int depth = 0;
public int minDepth2(TreeNode root) {
if (root == null) {
return 0;
}
dfs(root);
return result;
}
private void dfs(TreeNode node) {
depth++;
if (node.left == null && node.right == null) {
result = Math.min(result, depth);
return;
}
if (node.left != null) {
dfs(node.left);
depth--;
}
if (node.right != null) {
dfs(node.right);
depth--;
}
}
}