JZX轻语：简
LeetCode 671 - 二叉树中第二小的节点
发表于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)