671. 二叉树中第二小的节点

系统管理员 2023-10-04 08:11 24阅读 0赞

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 `2` 或 `0`。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。

更正式地说，`root.val = min(root.left.val, root.right.val)` 总成立。

给出这样的一个二叉树，你需要输出所有节点中的**第二小的值。**如果第二小的值不存在的话，输出 -1 **。**

**示例 1：**

![0bcc8d1bfd49276663468ef8e4c20907.png][]

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

**示例 2：**

![ac58c17f14a23e31dd1aa6a7c40abcc6.png][]

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

**提示：**

*  树中节点数目在范围 `[1, 25]` 内
 *  `1 <= Node.val <= 231 - 1`
 *  对于树中每个节点 `root.val == min(root.left.val, root.right.val)`

package Solution671;
    
    import java.util.Stack;
    import java.util.TreeSet;
    
    class Solution {
    
    	public int findSecondMinimumValue(TreeNode root) {
    		if (root == null) {
    			return -1;
    		}
    		TreeSet<Integer> ts = new TreeSet<Integer>();
    		Stack<TreeNode> stack = new Stack<>();
    		stack.push(root);
    		while (!stack.isEmpty()) {
    			TreeNode node = stack.pop();
    			ts.add(node.val);
    			if (node.right != null) {
    				stack.push(node.right);
    			}
    			if (node.left != null) {
    				stack.push(node.left);
    			}
    		}
    		if (ts.size() > 1) {
    			ts.pollFirst();
    			return ts.pollFirst();
    		}
    		return -1;
    	}
    
    	public static void main(String[] args) {
    
    		Solution same = new Solution();
    
    		TreeNode first = new TreeNode(1);
    		// first.left = new TreeNode(9);
    		first.right = new TreeNode(2);
    		first.right.left = new TreeNode(3);
    		// first.right.right = new TreeNode(7);
    
    		System.out.println(same.findSecondMinimumValue(first));
    	}
    
    }

[0bcc8d1bfd49276663468ef8e4c20907.png]: https://img-blog.csdnimg.cn/img_convert/0bcc8d1bfd49276663468ef8e4c20907.png
[ac58c17f14a23e31dd1aa6a7c40abcc6.png]: https://img-blog.csdnimg.cn/img_convert/ac58c17f14a23e31dd1aa6a7c40abcc6.png