题目在这里，要求一个二叉树的倒数第二个小的值。二叉树的特点是父节点的值会小于子节点的值，父节点要么没有子节点，要不左右孩子节点都有。
分析一下，根据定义，跟节点的值肯定是二叉树中最小的值，剩下的只需要找到左右子树中比跟节点大的最小值就可以了。对于这个题目，还是考察的二叉树的搜索，第一印象是BFS。使用一个辅助队列存储遍历过程中的节点，遍历过程中，如果节点的值比结果中第二小的值还大，就不用继续把该节点及其所有的子节点入队了，这样可以节省时间。这里的辅助队列使用的是deque，在两端存取数据的复杂度都是O(1)，List取出第一个元素的复杂度是O(n）。代码如下：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution(object):
def findSecondMinimumValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
from collections import deque
if not root:
return -1
stack = deque([root])
ret = [root.val]
while stack:
node = stack.popleft()
if node:
if node.val > ret[-1]:
if len(ret) < 2:
ret.append(node.val)
else:
if ret[0] < node.val < ret[1]:
ret[1] = node.val
stack.append(node.left)
stack.append(node.right)
return ret[1] if len(ret) == 2 else -1
每次做完都要去讨论区看看有没有亮瞎眼的解法，把DFS的代码贴在下面，思路是一样的，不过看着更简洁了：
class Solution(object):
def findSecondMinimumValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# Time: O(n)
# Space: O(lgn)
res = [float('inf')]
def traverse(node):
if not node:
return
if root.val < node.val < res[0]:
res[0] = node.val
traverse(node.left)
traverse(node.right)
traverse(root)
return -1 if res[0] == float('inf') else res[0]
这里需要说一下代码中的float('inf')，以前倒是真没用到这里，这是Python中代表正无穷的写法，负无穷就是float('-inf')了，又了解了一个新内容，嘿嘿。