[二叉数]二叉树的最小深度(递归和迭代做法)
一、题目描述
示例 1：
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
**说明：**叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
提示：
-
树中节点数的范围在 [0, 10^5] 内 -1000 <= Node.val <= 1000
二、思路分析
其实之前我们做过一次这道题，但是用的层次遍历，层次遍历那是真香呀，可以一打十题！可以看看！ 我们还了解过迭代遍历和递归遍历！那我们在聊一聊这两个！ 首先递归遍历，老样子，三部曲：
-
参数和返回值类型，返回值不用犹豫就是int，参数的话需要传递二叉树，而且还需要传递深度，所以两个参数public int getMinDepth(TreeNode root, int deepth) 中止条件就是如果树为空则返回当前深度！ 单层遍历（我们用后序遍历举例）就是第一遍历左子树，第二遍历右子树，第三就是如果左子树为空，右子树不为空则返回左子树的深度（毕竟最小深度嘛），如果左子树不为空，右子树为空，则然会右子树高度，否则返回左右子树的最小值！
迭代遍历的话，需要注意的点就是左右子树都为空才返回深度！
三、AC代码
递归做法：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
return getMinDepth(root, 0);
}
public int getMinDepth(TreeNode root, int deepth){
if (root == null) return deepth;
int leftDeepth = getMinDepth(root.left, deepth + 1);
int rightDeepth = getMinDepth(root.right, deepth + 1);
if (root.left == null && root.right != null){
return rightDeepth;
}
if (root.left != null && root.right == null){
return leftDeepth;
}
return leftDeepth > rightDeepth ? rightDeepth : leftDeepth ;
}
}
迭代做法：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
if (root != null) deque.offer(root);
int depth = 0;
while (!deque.isEmpty()){
int len = deque.size();
depth++;
while (len > 0){
TreeNode tmpNode = deque.poll();
if (tmpNode.left != null) deque.offer(tmpNode.left);
if (tmpNode.right != null) deque.offer(tmpNode.right);
if (tmpNode.left == null && tmpNode.right == null) return depth;
len--;
}
}
return depth;
}
}
四、总结
-
二叉树的迭代和递归遍历复习！
感谢大家的阅读，我是Alson_Code，一个喜欢把简单问题复杂化，把复杂问题简单化的程序猿！ ❤