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

Question

我正在写代码来计算二叉树的最小深度
我的解决方案适用于树BST，如果输入是6,4,9,3,5,7,12,2,8
因为最小深度是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中有一个返回值。
• 更多的代码(TreeNode类和main)将是有用的