【JAVA】【leetcode】【查找二叉树最小深度】

时间:2023-03-08 22:59:52
【JAVA】【leetcode】【查找二叉树最小深度】

题目:  minimum-depth-of-binary-tree

要求:Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

思路:

两种方法:
第一,使用递归,相当于遍历了整个二叉树,递归返回深度浅的那棵子树的深度。
第二,按层检查有没有叶子节点,有的话停止检查,返回当前层数。至于实现这个按层检查,可以用递归的方法。该法不用遍历整个树。
                                                          --来自于牛客426550号
由于我本人只想到第一种办法,看到牛客友人牛客426550号给的思路觉得考虑的比较周全,所以就在此引用一下。谢谢!
递归要分清楚几种情况:
1、当根节点为空时,返回0
2、当只有左子节点(无右子节点)时,返回 1
3、当只有右子节点(无左子节点)时,返回 1
4、当左右子节点都存在时,分别计算左子树和右子树的深度,min(左子树最小深度,右子树最小深度)+1
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
} public class Solution {
public int run(TreeNode root) {
if(root!=null){
int left = Integer.MAX_VALUE;
int right = Integer.MAX_VALUE;
if(root.left!=null){
left = run(root.left);
}
if(root.right!=null){
right = run(root.right);
}
if(left<right){
return left+1;
}
else if(left>right){
return right+1;
}
else if(left==right&&left!=Integer.MAX_VALUE){
return left+1;
}
else
return 1;
}
return 0; }
}

当然,还有一个较简洁的递归方法,最核心的思想就是根节点到达最近的叶子节点的路径长度:

1、当根为空时,输出0

2、当左子树为空时,输出右子树深度+1

3、当右子树为空时,输出左子树深度+1

4、以上条件都不满足时,输出min(左子树深度,右子树深度)+1

public class Solution {
public int run(TreeNode root) {
if(root==null)
return 0;
if(root.left==null)
return run(root.right)+1;
if(root.right==null)
return run(root.left)+1;
return Math.min(run(root.left),run(root.right))+1; }
}

相关文章