Skip to content

671. Second Minimum Node In a Binary Tree 👎

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int findSecondMinimumValue(TreeNode* root) {
    if (root == nullptr)
      return -1;
    return findSecondMinimumValue(root, root->val);
  }

 private:
  int findSecondMinimumValue(TreeNode* root, int mn) {
    if (root == nullptr)
      return -1;
    if (root->val > mn)
      return root->val;

    const int leftMin = findSecondMinimumValue(root->left, mn);
    const int rightMin = findSecondMinimumValue(root->right, mn);

    if (leftMin == -1 || rightMin == -1)
      return max(leftMin, rightMin);
    return min(leftMin, rightMin);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int findSecondMinimumValue(TreeNode root) {
    if (root == null)
      return -1;
    return findSecondMinimumValue(root, root.val);
  }

  private int findSecondMinimumValue(TreeNode root, int mn) {
    if (root == null)
      return -1;
    if (root.val > mn)
      return root.val;

    final int leftMin = findSecondMinimumValue(root.left, mn);
    final int rightMin = findSecondMinimumValue(root.right, mn);

    if (leftMin == -1 || rightMin == -1)
      return Math.max(leftMin, rightMin);
    return Math.min(leftMin, rightMin);
  }
}