查找 BST 的最小深度 ... findHeight 函数将不起作用
Finding minimum depth of BST ... findHeight function won't work
尝试轻松解决此 LC:https://leetcode.com/problems/minimum-depth-of-binary-tree/
也就是求一棵树的最小深度(最短路径上的节点数)
我能够创建一个“findheight”函数来计算树的高度。
我的逻辑是使用 findheight 找到根节点的两个子树(左和右)的高度,然后 return 两个高度之间的最小值。
class Solution {
public int minDepth(TreeNode root) {
if(root == null){return 0;}
int left = findHeight(root.left);
int right = findHeight(root.right);
//unbalanced tree, only one subtree
if(left == 0 || right == 0){
return Math.max(left,right) + 1;
}
return Math.min(left,right) + 1 ;
}
public int findHeight(TreeNode root){
if(root == null){return 0;}
int left = findHeight(root.left);
int right = findHeight(root.right);
return Math.max(left,right) + 1;
}
}
它不会通过测试用例:
[-9,-3,2,null,4,4,0,-6,null,-5]
或者:
Output:
4
Expected:
3
我现在的想法是,当我使用“findHeight”时,我 return 返回每个左右子树的 'max' 高度。在这个测试用例中,我应该 return 返回最小高度。
我在另一次迭代中将我的代码更改为“Math.min”,但这也不起作用。
有什么想法或理论吗?如此迷茫!!我应该完全放弃这种方法吗?
当前代码中的问题
//unbalanced tree, only one subtree
if(left == 0 || right == 0){
return Math.max(left,right) + 1;
}
以上代码行仅检查 root level
处的不平衡。它不会递归检查较低级别的不平衡。
检查每个级别的不平衡
public int minDepth(final TreeNode node) {
if (node == null) {
return 0;
}
final int left = minDepth(node.left);
final int right = minDepth(node.right);
// if both paths exist, then return the minimum
if (node.left != null && node.right != null) {
return Math.min(left, right) + 1;
} else {
// if zero or one path exists return that path (so take maximum)
return Math.max(left, right) + 1;
}
}
尝试轻松解决此 LC:https://leetcode.com/problems/minimum-depth-of-binary-tree/
也就是求一棵树的最小深度(最短路径上的节点数)
我能够创建一个“findheight”函数来计算树的高度。
我的逻辑是使用 findheight 找到根节点的两个子树(左和右)的高度,然后 return 两个高度之间的最小值。
class Solution {
public int minDepth(TreeNode root) {
if(root == null){return 0;}
int left = findHeight(root.left);
int right = findHeight(root.right);
//unbalanced tree, only one subtree
if(left == 0 || right == 0){
return Math.max(left,right) + 1;
}
return Math.min(left,right) + 1 ;
}
public int findHeight(TreeNode root){
if(root == null){return 0;}
int left = findHeight(root.left);
int right = findHeight(root.right);
return Math.max(left,right) + 1;
}
}
它不会通过测试用例:
[-9,-3,2,null,4,4,0,-6,null,-5]
或者:
Output:
4
Expected:
3
我现在的想法是,当我使用“findHeight”时,我 return 返回每个左右子树的 'max' 高度。在这个测试用例中,我应该 return 返回最小高度。
我在另一次迭代中将我的代码更改为“Math.min”,但这也不起作用。
有什么想法或理论吗?如此迷茫!!我应该完全放弃这种方法吗?
当前代码中的问题
//unbalanced tree, only one subtree
if(left == 0 || right == 0){
return Math.max(left,right) + 1;
}
以上代码行仅检查 root level
处的不平衡。它不会递归检查较低级别的不平衡。
检查每个级别的不平衡
public int minDepth(final TreeNode node) {
if (node == null) {
return 0;
}
final int left = minDepth(node.left);
final int right = minDepth(node.right);
// if both paths exist, then return the minimum
if (node.left != null && node.right != null) {
return Math.min(left, right) + 1;
} else {
// if zero or one path exists return that path (so take maximum)
return Math.max(left, right) + 1;
}
}