查找二叉树的最小深度

Question

我需要找到二叉树的最小深度。我的代码在此测试用例上失败：[-9, -3, 2, null, 4, 4, 0, -6, null, -5] .

给定一个二叉树，找到它的最小深度示例：

给定二叉树[3, 9, 20, null, null, 15, 7]，

    3
   / 
  9  20
    /  
   15   7

返回其最小深度 = 2。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int count(TreeNode root) { 
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(count(root.left), count(root.right));
    }
    public int minDepth(TreeNode root) {
        int left = 0, right = 0;
        if (root == null) {
            return 0;
        }
        if (root.right == null) {
           return  1 + count(root.left);
        }      
        if (root.left == null) {
            return  1 + count(root.right);
        }
        left = count(root.left);
        right = count(root.right);
        return  1 + Math.min(left, right);
    }
}

• 输出 = 4
• 预期 = 3

Answer 1

我相信问题在于使用Math.max而不是Math.min

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

Answer 2

帮助程序函数在这里似乎矫枉过正; 将所有逻辑放入一个函数中并传递堆栈计数更容易。

有3种情况：

• 如果此节点为 null，则返回 0。
• 如果没有子节点，则此节点为叶。返回 1。
• 如果有左子节点和/或右子节点，则此节点是内部节点。递归计算任何当前子节点的最小深度，并加 1 以计数当前节点。如果缺少左子项或右子项，我们将在计算中将其最小值合并为无穷大来忽略它。

代码如下：

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    else if (root.left == null && root.right == null) {
        return 1;
    }
    int left = root.left == null ? Integer.MAX_VALUE : minDepth(root.left);
    int right = root.right == null ? Integer.MAX_VALUE : minDepth(root.right);
    return Math.min(left, right) + 1;
}