java - 在二叉树中找到最小值？

Question

我试图找到二叉树的最小值，而不是二叉搜索树，但无法得到答案，代码如下。请告诉我出了什么问题。编辑:因此，在海报的帮助下，我能够使代码正常工作。我使代码 1 可以工作，但我不明白为什么在代码 2 中我们需要再次检查 Math.min，而在代码 1 中我们不需要这样做。

代码1:

    static int min = 0;
    static public int findMinimumValue(Node root) {
       min = root.data;
           findMinimumValue(root, root.data);
           return min;
   }
      static public int findMinimumValue(Node root, int x) {

          if(root == null) {
                return min;
            } else {
                if(root.data < min) {

                    min = root.data;
                }
                int left = findMinimumValue(root.left, x);
                int right = findMinimumValue(root.right, x);
               return min;

            }
        }

代码2:

   static public int findSecondMinimumValue(Node root) {
      // min = root.data;
        return findSecondMinimumValue(root, root.data);
 }
    static public int findSecondMinimumValue(Node root, int min) {

        if(root == null) {
              return min;
          } else {
              if(root.data < min) {

                  min = root.data;
              }
              int left = findSecondMinimumValue(root.left, min);
              int right = findSecondMinimumValue(root.right, min);


            return Math.min(left, right);
          }
      }

Answer 1

第 1 步:确定问题

按照您在代码库中所做的一切进行操作。让我们制作一棵二叉树:

      5
    /  \
   2    1

显然最小值是 1，对吗？因此，请按照此示例完成您的代码。

public int findMinimumValue(TreeNode root) {
    return findMinimumValue(root, root.val);
}

根将是起点。

        int left = findMinimumValue(root.left, min);
        int right = findMinimumValue(root.right, min);

这是每个节点都会看到的内容(如果它不为空)。这是向左递归调用，然后在尽可能向左移动后向右递归调用。

finalMinimumValue(TreeNode(5), 5)

调用以下内容:

int left = finalMinimumValue(TreeNode(2), 5);
int right = finalMinimumValue(TreeNode(1), 5)

finalMinimumValue(TreeNode(2), 5)

调用以下内容:

int left = finalMinimumValue(null, 5);
int right = finalMinimumValue(null, 5)

finalMinimumValue(null, 5)

执行以下代码:

return min;

什么是分钟？分钟是 5。

这有道理吗？我们遍历了超过 2 个，但仍将最小值保持为 5。

第 2 步:解决问题

我们在步骤 1 中得出的结论是，如果我们当前所在的节点不是最小值，那么不更新 min 是没有意义的。因此，让我们在递归下去之前先更新它。

public int findMinimumValue(TreeNode root) {
    return findMinimumValue(root, root.val);
}

public int findMinimumValue(TreeNode root, int min) {

    if (root == null) {
        return min;
    } else {
        // update your min variable here by comparing it with the node you currently are at!

        int left = findMinimumValue(root.left, min);
        int right = findMinimumValue(root.right, min);
        if (left < min) {
            min = left;
        }
        if (right < min) {
            min = right;
        }
        return min;
    }
}

第 3 步:测试解决方案

让我们继续使用相同的示例。我们预计它会说它是 1。

      5
    /  \
   2    1

1:计算根节点的left

我们的节点的值是 5。5 是否比我们的节点的值 (5) 小？不。所以，不要更新最小值。

接下来，调用左子节点，Node(2)

2:计算节点 2 返回的最小值

我们的节点的值是 2。5 比我们的节点的值 (2) 小吗？是的!因此，更新我们的最小值。

现在最小值是 2。

接下来，调用左子元素null。由于它的左子节点为 null，因此我们返回 min，即 2。

现在，调用右子元素null。由于它的右子节点为 null，因此我们返回 min，即 2。

好吧，左边等于 2，右边等于 2。所以，返回 2!

3:计算节点 1 返回的最小值

我们的节点的值是 1。5 比我们的节点的值 (1) 小吗？是的!因此更新最小值。

现在最小值是 1。

接下来，调用左子元素null。由于它的左子节点为 null，因此我们返回 min，即 1。

现在，调用右子元素null。由于它的右子节点为 null，因此我们返回 min，即 1。

好吧，左边等于 1，右边等于 1。所以，返回 1!

4:计算根节点返回的最小值。

左边返回了我们2。右边返回给我们 1。

由于 1 小于 2，因此答案为 1。

它有效!