Easy

题目描述

给定一个非空特殊的二叉树，该二叉树由具有非负值的节点组成，其中该树中的每个节点都恰好有两个或零个子节点。如果一个节点有两个子节点，那么该节点的值是其两个子节点中较小的值。更正式地说，属性 root.val = min(root.left.val, root.right.val) 始终成立。

给定这样的二叉树，你需要输出整个树中所有节点值组成的集合中的第二小值。

如果不存在这样的第二小值，则输出 -1。

示例 1：

输入：root = [2,2,5,null,null,5,7]
输出：5
解释：最小值是 2，第二小值是 5。

示例 2：

输入：root = [2,2,2]
输出：-1
解释：最小值是 2，但不存在第二小值。

约束条件：

  • 树中节点数量范围是 [1, 25]
  • 1 <= Node.val <= 2³¹ - 1
  • 对于树中每个内部节点，都有 root.val == min(root.left.val, root.right.val)

解题思路

解题思路

这道题的关键是理解特殊二叉树的性质：每个节点的值都是其子节点中的最小值。这意味着根节点一定是整棵树的最小值。

基本分析：

  1. 根节点值就是全树的最小值
  2. 第二小的值一定出现在某个节点中，且该值大于根节点值
  3. 由于父节点总是子节点的最小值，如果某个节点值等于根节点值，那么它的子树中不可能有更小的值

解法思路： 使用深度优先搜索（DFS）遍历整棵树。在遍历过程中：

  • 如果当前节点值等于根节点值，继续遍历其子树
  • 如果当前节点值大于根节点值，这个值就是候选的第二小值
  • 由于树的性质，如果某节点值大于根节点值，其子树中的所有值都不会小于该节点值，可以进行剪枝

优化策略：

  1. 一旦找到比根节点大的值，就不需要继续遍历该子树
  2. 维护当前找到的第二小值，用于进一步剪枝

代码实现

class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        if (!root) return -1;
        return dfs(root, root->val);
    }
    
private:
    int dfs(TreeNode* node, int first) {
        if (!node) return -1;
        
        if (node->val > first) {
            return node->val;
        }
        
        int left = dfs(node->left, first);
        int right = dfs(node->right, first);
        
        if (left == -1) return right;
        if (right == -1) return left;
        
        return min(left, right);
    }
};

class Solution:
    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        if not root:
            return -1
        
        def dfs(node, first):
            if not node:
                return -1
            
            if node.val > first:
                return node.val
            
            left = dfs(node.left, first)
            right = dfs(node.right, first)
            
            if left == -1:
                return right
            if right == -1:
                return left
            
            return min(left, right)
        
        return dfs(root, root.val)

public class Solution {
    public int FindSecondMinimumValue(TreeNode root) {
        if (root == null) return -1;
        return DFS(root, root.val);
    }
    
    private int DFS(TreeNode node, int first) {
        if (node == null) return -1;
        
        if (node.val > first) {
            return node.val;
        }
        
        int left = DFS(node.left, first);
        int right = DFS(node.right, first);
        
        if (left == -1) return right;
        if (right == -1) return left;
        
        return Math.Min(left, right);
    }
}

var findSecondMinimumValue = function(root) {
    function dfs(node) {
        if (!node) return -1;
        
        if (node.val > root.val) {
            return node.val;
        }
        
        const left = dfs(node.left);
        const right = dfs(node.right);
        
        if (left === -1) return right;
        if (right === -1) return left;
        
        return Math.min(left, right);
    }
    
    return dfs(root);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)最坏情况下需要遍历所有节点，其中 n 是树中节点的数量
空间复杂度O(h)递归调用栈的深度，其中 h 是树的高度，最坏情况下为 O(n)

相关题目