Java: 二叉搜索树递归的最小深度

Question

我正在编写代码来计算二叉树的最小深度
如果输入为 6,4,9,3,5,7,12,2,8
，我的解决方案适用于树 BST 因为最小深度为 3，这是正确的。
但是当树为 3,2 时，最小深度为 1 而不是 2.
我的代码片段是：

int minimumHeightRec(TreeNode root)
        {
            if(root == null) return 0;
            int left = minimumHeightRec(root.left);
            int right = minimumHeightRec(root.right);
            if(left > right) return right + 1;
            else return left + 1;
        }

Answer 1

您的实施是正确的。预期的 minHeight 应该是 1 而不是 2。考虑您的 [3, 2] 示例，BST 可能具有以下形式：

  3
 /
2

查看 root 的 left 的高度为 2：(3) -> (2)

查看 root 的 right 高度为 1: (3)

你正在寻找BST的minHeight，所以取高度的右分支1是正确的选择。

请注意，您可能有不同的树形式，其中 2 是根，但逻辑和结果是相同的。

Answer 2

else没有用，因为if里有return
更多代码（TreeNode class 和 main）会很有用。

Java: 二叉搜索树递归的最小深度

Java: Minimum Depth of Binary search Tree Recursive

java

algorithm

tree

recursion

binary-search-tree