二叉树的最小深度
题目链接描述示例初始代码模板代码BFSDFS
题目链接
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明
: 叶子节点是指没有子节点的节点。
示例
给定二叉树
[3,9,20,null
,null
,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度
2.
初始代码模板
class Solution {
public int minDepth(TreeNode root
) {
}
}
代码
很容易想到的思路，就是层序遍历，遇到叶子节点返回当前深度即可
BFS
class Solution {
public int minDepth(TreeNode root
) {
if (root
== null
) {
return 0;
}
LinkedList
<TreeNode> queue
= new LinkedList<>();
queue
.offer(root
);
int res
= 1;
while (!queue
.isEmpty()) {
for (int i
= queue
.size(); i
> 0; i
--) {
TreeNode node
= queue
.poll();
if (node
.left
== null
&& node
.right
== null
) {
return res
;
}
if (node
.left
!= null
) {
queue
.offer(node
.left
);
}
if (node
.right
!= null
) {
queue
.offer(node
.right
);
}
}
res
++;
}
return res
;
}
}
DFS
注意叶子节点即可
class Solution {
public int minDepth(TreeNode root
) {
if (root
== null
) {
return 0;
}
int left
= minDepth(root
.left
);
int right
= minDepth(root
.right
);
return left
== 0 || right
== 0? right
+ left
+ 1 : Math
.min(left
, right
) + 1;
}
}
