查找二叉树的最小高度...代码缺少 1 个小编辑以通过所有测试用例

Question

我正在尝试找出一棵树的最小高度。我修改了我原来的算法来找到一棵树的最大高度（但这次，只使用 Math.min 而不是 Math.max）。

/**
 * 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) {
        if(root == null){return Integer.MAX_VALUE;}
        if(root.left == null && root.right == null){return 1;}
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return Math.min(left, right) + 1;
    }
}

它能够通过普通树，Integer.MAX_VALUE用于

的测试用例

但是，代码将无法通过简单输入为空的“[]”的测试用例。

我可以对此代码进行任何更改以使其通过吗？我挠头想知道是否应该删除它并从头开始。不过我觉得很亲近。

LC 问题：https://leetcode.com/problems/minimum-depth-of-binary-tree/

Answer 1

您的代码中的问题是，例如当树倾斜时，它会 return 到目前为止它遍历的子树的最小深度值。如果您考虑以下树：

应该return-2147483648.

仔细查看root的左右子树，分别是2,

left subtree depth value: Integer.MAX_VALUE (+1) = -2147483648
right subtree depth value: 4 (+1) = 5

现在检查下一个元素 3,

 minimum value found so far: -2147483648
 right subtree depth value: 3 (+1) = 4

现在检查下一个元素，即 4、

 minimum value found so far: -2147483648
 right subtree depth value: 2 (+1) = 3

等等..最后会得出我们目前找到的最小数量，即-2147483648或者在2147483647的情况下树是[=21] =] 或 null.

您需要更改逻辑，在这种情况下，最大深度节点应采用最小深度值：

我为你写了一个解决方案，检查它是否有效：

int min = Integer.MAX_VALUE;
public int minDepth(TreeNode root) {
    if(root == null){
        return 0; /* return 0 when the tree is empty */
    }
    /* visit each node in DFS manner, and found maximum depth-ed node possible */
    minDepth(root, 0);
    return min+1;
}

private void minDepth(TreeNode root, int count){
    if(root == null){
        return;
    }else if(root.left == null && root.right == null){
        /* replace the minimum value with maximum-depth node counter */
        if(min > count){
            min = count;
        }
    }else{
        count += 1;
        minDepth(root.left, count);
        minDepth(root.right, count);
    }

查找二叉树的最小高度...代码缺少 1 个小编辑以通过所有测试用例

Finding minimum height of binary tree...code missing 1 minor edit to pass all test cases

java

tree

binary-tree

binary-search-tree