发表于 2024.04.16

• 有两种做法：一种就是遍历树，不断更新第二小的结果，如果当前节点的值大于当前结果，则剪枝以加快处理；

  另外一种则是使用同一个函数进行递归处理：如果当前节点为空或为叶节点，则返回-1；否则，递归检查左右子树的结果：如果左孩子的值等于右孩子（同样等于该节点的值），则取左右子树结果中的最小者返回；如果两孩子值不相等，则先遍历最小者的子树，若结果为-1，则直接返回较大的孩子值，否则返回该结果。

  第一种做法：

  from collections import deque
  
  
  class Solution:
      def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
          ans, min_val = -1, root.val
          q = deque()
          q.append(root)
          while q:
              node = q.popleft()
              if node is None:
                  continue
              if node.val > min_val:
                  if ans == -1 or node.val < ans:
                      ans = node.val
                  else:
                      continue
              q.append(node.left)
              q.append(node.right)
          return ans

  第二种做法：

  class Solution:
      def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
          if root is None or (root.left is None):
              return -1
  
          if root.left.val == root.right.val:
              lr = self.findSecondMinimumValue(root.left)
              rr = self.findSecondMinimumValue(root.right)
              if -1 in (lr, rr):
                  return max(lr, rr)
              return min(lr, rr)
          min_child, max_child = (root.left, root.right) if root.left.val < root.right.val else (root.right, root.left)
          lr = self.findSecondMinimumValue(min_child)
          if lr == -1:
              return max_child.val
          return min(lr, max_child.val)

• LC 题目链接