查找 BST 的最小深度 ... findHeight 函数将不起作用

Question

尝试轻松解决此 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”，但这也不起作用。

有什么想法或理论吗？如此迷茫！！我应该完全放弃这种方法吗？

Answer 1

当前代码中的问题

//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;
        }
    }

查找 BST 的最小深度 ... findHeight 函数将不起作用

Finding minimum depth of BST ... findHeight function won't work

java

binary-search-tree

depth-first-search

breadth-first-search

depth

当前代码中的问题

检查每个级别的不平衡