难度: Easy
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
更正式地说，即 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 <= 231 - 1root.val == min(root.left.val, root.right.val)运行时间: 23 ms
内存: 16.1 MB
class Solution:
def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
q=[root]
a=2**32
b= 2**32
d=2**32
while q :
c = q.pop()
if c.right:q.append(c.right)
if c.left:q.append(c.left)
if c.val<=a:a=c.val
elif c.val<b :b=c.val
if a==d or b==d :return -1
return b
这个题解采用 BFS 的思路来遍历二叉树。首先初始化两个变量 a 和 b 来分别存储最小值和第二小的值，初始值均为无穷大。然后使用一个队列 q 来进行 BFS 遍历，每次从队列中取出一个节点，并将其左右子节点（如果存在）加入队列。在遍历过程中，不断更新 a 和 b 的值，如果当前节点的值小于等于 a，则更新 a；如果当前节点的值大于 a 且小于 b，则更新 b。最后，如果 a 或 b 的值仍为初始值（无穷大），说明不存在第二小的值，返回 -1，否则返回 b。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
q=[root] # 初始化队列，将根节点加入队列
a=2**32 # 初始化最小值为无穷大
b= 2**32 # 初始化第二小的值为无穷大
d=2**32 # 初始化一个辅助变量为无穷大
while q : # BFS 遍历二叉树
c = q.pop() # 从队列中取出一个节点
if c.right:q.append(c.right) # 如果当前节点有右子节点，将其加入队列
if c.left:q.append(c.left) # 如果当前节点有左子节点，将其加入队列
if c.val<=a:a=c.val # 如果当前节点的值小于等于最小值，更新最小值
elif c.val<b :b=c.val # 如果当前节点的值大于最小值且小于第二小的值，更新第二小的值
if a==d or b==d :return -1 # 如果最小值或第二小的值仍为无穷大，说明不存在第二小的值，返回 -1
return b # 返回第二小的值
在题解中，变量a用于追踪树中的最小值，变量b用于追踪第二小的值。这两个变量被初始化为无穷大是为了确保在遍历过程中能够正确地更新它们，即只有当遇到比当前记录更小的值时，才进行更新。变量d则用作一个辅助变量，同样初始化为无穷大，它的主要作用是在最后判断a和b是否被有效更新过。如果a或b在遍历结束后仍然等于d（无穷大），则说明树中不存在一个或两个这样的有效值。
如果二叉树中所有节点的值相同，则a会在遍历第一个节点时被更新为该共同值，但b将永远不会被更新，因为没有任何节点的值大于a且小于无穷大。例如，对于一个只包含值3的二叉树（所有节点值为3），a将更新为3，而b则保持为无穷大。此外，如果树只有一个节点，那么a会被更新为那个单一节点的值，但b不会被更新，因为没有第二个节点的值来进行比较。
BFS和DFS都可以用来解决这个问题，但BFS提供了一种层次遍历的方式，这可能在某些情况下更快地找到第二小的值，尤其是如果第二小的值出现在树的较低层。BFS确保一旦找到第二小的值就可以停止进一步的遍历，从而可能提高效率。然而，DFS可能需要遍历更多的节点才能确定第二小的值，尤其是在深度较大的树中。总的来说，选择BFS或DFS主要取决于具体的树结构和数据分布。
是的，这种更新方式可以保证最终b是树中第二小的值。这是因为算法首先通过不断更新a找到最小值。一旦a被确定，算法就会寻找大于a且最接近a的值去更新b。因此，任何更新b的值都必然大于a且是遍历过程中遇到的最小的这样的值，确保了b是第二小的值。如果所有节点值都大于a或等于a，b将不会被更新，最终检查会返回-1，表示第二小的值不存在。