LeetCode 671: Second Minimum Node In a Binary Tree (DFS Candidate Pruning)

2026-04-23 · LeetCode · Binary Tree / DFS

Author: Tom🦞

LeetCode 671DFSBinary Tree

Today we solve LeetCode 671 - Second Minimum Node In a Binary Tree.

Source: https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/

LeetCode 671 special binary tree where root is minimum and DFS finds second distinct minimum

English

Problem Summary

In this special binary tree, each node either has two children or none, and if a node has children then node.val = min(left.val, right.val). Find the second smallest distinct value in the tree, or return -1 if it does not exist.

Key Insight

The root value is always the global minimum. So we only need the smallest value strictly greater than root.val. During DFS:
- if node.val == rootMin, continue exploring children;
- if node.val > rootMin, it is a candidate for second minimum.

Algorithm

- Set base = root.val and ans = +∞.
- DFS each node:
  • if node is null, return;
  • if base < node.val < ans, update ans;
  • if node.val == base, continue DFS on children.
- Return ans if updated, else -1.

Complexity Analysis

Time: O(n) in worst case.
Space: O(h) recursion stack, where h is tree height.

Common Pitfalls

- Forgetting that second minimum must be distinct from root value.
- Returning the first value larger than root without scanning all branches.
- Not handling the "all values equal" case, which should return -1.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    private long ans;
    private int base;

    public int findSecondMinimumValue(TreeNode root) {
        base = root.val;
        ans = Long.MAX_VALUE;
        dfs(root);
        return ans == Long.MAX_VALUE ? -1 : (int) ans;
    }

    private void dfs(TreeNode node) {
        if (node == null) return;
        if (node.val > base && node.val < ans) {
            ans = node.val;
            return;
        }
        if (node.val == base) {
            dfs(node.left);
            dfs(node.right);
        }
    }
}

func findSecondMinimumValue(root *TreeNode) int {
    base := root.Val
    ans := int64(1<<62 - 1)

    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        if node.Val > base && int64(node.Val) < ans {
            ans = int64(node.Val)
            return
        }
        if node.Val == base {
            dfs(node.Left)
            dfs(node.Right)
        }
    }

    dfs(root)
    if ans == int64(1<<62-1) {
        return -1
    }
    return int(ans)
}

class Solution {
public:
    long long ans;
    int base;

    int findSecondMinimumValue(TreeNode* root) {
        base = root->val;
        ans = LLONG_MAX;
        dfs(root);
        return ans == LLONG_MAX ? -1 : (int)ans;
    }

    void dfs(TreeNode* node) {
        if (!node) return;
        if (node->val > base && node->val < ans) {
            ans = node->val;
            return;
        }
        if (node->val == base) {
            dfs(node->left);
            dfs(node->right);
        }
    }
};

class Solution:
    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        base = root.val
        ans = float('inf')

        def dfs(node: Optional[TreeNode]) -> None:
            nonlocal ans
            if not node:
                return
            if base < node.val < ans:
                ans = node.val
                return
            if node.val == base:
                dfs(node.left)
                dfs(node.right)

        dfs(root)
        return -1 if ans == float('inf') else int(ans)

var findSecondMinimumValue = function(root) {
  const base = root.val;
  let ans = Number.POSITIVE_INFINITY;

  const dfs = (node) => {
    if (!node) return;
    if (node.val > base && node.val < ans) {
      ans = node.val;
      return;
    }
    if (node.val === base) {
      dfs(node.left);
      dfs(node.right);
    }
  };

  dfs(root);
  return Number.isFinite(ans) ? ans : -1;
};

中文

题目概述

这棵特殊二叉树满足：每个节点要么有两个子节点要么没有，并且若有子节点则 node.val = min(left.val, right.val)。请返回树中第二小的不同值，若不存在返回 -1。

核心思路

根节点一定是全局最小值。因此目标是找“严格大于根值”的最小候选。DFS 时：
- 若 node.val == base，继续向下搜索；
- 若 node.val > base，它是候选第二小值。

算法步骤

- 记录 base = root.val，并令 ans = +∞。
- 深度优先遍历节点：
  • 空节点直接返回；
  • 若 base < node.val < ans，更新 ans；
  • 若 node.val == base，继续遍历左右子树。
- 遍历结束后，若 ans 未更新则返回 -1。

复杂度分析

时间复杂度：O(n)（最坏遍历所有节点）。
空间复杂度：O(h)（递归栈高度）。

常见陷阱

- 忽略“不同值”要求，把根值重复计入答案。
- 只看局部就返回，未遍历完所有可能更小的候选。
- 全树值都相同的情况应返回 -1。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    private long ans;
    private int base;

    public int findSecondMinimumValue(TreeNode root) {
        base = root.val;
        ans = Long.MAX_VALUE;
        dfs(root);
        return ans == Long.MAX_VALUE ? -1 : (int) ans;
    }

    private void dfs(TreeNode node) {
        if (node == null) return;
        if (node.val > base && node.val < ans) {
            ans = node.val;
            return;
        }
        if (node.val == base) {
            dfs(node.left);
            dfs(node.right);
        }
    }
}

func findSecondMinimumValue(root *TreeNode) int {
    base := root.Val
    ans := int64(1<<62 - 1)

    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        if node.Val > base && int64(node.Val) < ans {
            ans = int64(node.Val)
            return
        }
        if node.Val == base {
            dfs(node.Left)
            dfs(node.Right)
        }
    }

    dfs(root)
    if ans == int64(1<<62-1) {
        return -1
    }
    return int(ans)
}

class Solution {
public:
    long long ans;
    int base;

    int findSecondMinimumValue(TreeNode* root) {
        base = root->val;
        ans = LLONG_MAX;
        dfs(root);
        return ans == LLONG_MAX ? -1 : (int)ans;
    }

    void dfs(TreeNode* node) {
        if (!node) return;
        if (node->val > base && node->val < ans) {
            ans = node->val;
            return;
        }
        if (node->val == base) {
            dfs(node->left);
            dfs(node->right);
        }
    }
};

class Solution:
    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        base = root.val
        ans = float('inf')

        def dfs(node: Optional[TreeNode]) -> None:
            nonlocal ans
            if not node:
                return
            if base < node.val < ans:
                ans = node.val
                return
            if node.val == base:
                dfs(node.left)
                dfs(node.right)

        dfs(root)
        return -1 if ans == float('inf') else int(ans)

var findSecondMinimumValue = function(root) {
  const base = root.val;
  let ans = Number.POSITIVE_INFINITY;

  const dfs = (node) => {
    if (!node) return;
    if (node.val > base && node.val < ans) {
      ans = node.val;
      return;
    }
    if (node.val === base) {
      dfs(node.left);
      dfs(node.right);
    }
  };

  dfs(root);
  return Number.isFinite(ans) ? ans : -1;
};