【Leetcode Daily】671二叉树中第二小的节点

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个二叉树，规定其中的每个节点值，满足一个节点如果有两个子节点，那么这个值就是子节点的最小值，且除叶子节点以外节点均有两个子节点。求整个二叉树的第二小的值。

思路分享

• 一开始突然觉得 bfs 会不会表现更好，遇到比答案更大节点就返回会不会更快。但是这个思维忽略了更小的节点可能藏在更深的层次的情况，所以最终还是要遍历整个二叉树。

• 那么怎么记录这个第二小的值呢？一开始想的是堆，python 默认小顶堆，直接管上。但其实不必要，毕竟最终就要一个值，所以其实只要维护一个大于根节点中的最小值即可。

• 这位灵茶山土地的答案挺不错。

  https://leetcode.cn/problems/second-minimum-node-in-a-binary-tree/solutions/3645006/ling-shen-ke-hou-qian-xu-bian-li-by-zhi-oc3tc/

代码解答（强烈建议自行解答后再看）

• 参考题解

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        min_num = root.val
        ans = inf
        def dfs(root: Optional[TreeNode]):
            if not root:
                return
            if root.val > min_num:
                nonlocal ans
                ans = ans if ans <= root.val else root.val
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return ans if ans < inf else -1

        # min_num = root.val
        # ans_heap = []
        # heapq.heapify(ans_heap)
        # def dfs(root: Optional[TreeNode]):
        #     if not root:
        #         return
        #     if root.val > min_num:
        #         nonlocal ans_heap
        #         heappush(ans_heap, root.val)
        #     dfs(root.left)
        #     dfs(root.right)
        # dfs(root)
        # return ans_heap[0] if len(ans_heap) > 0 else -1