一、671. 二叉树中第二小的节点

1.1、题目描述

1.2、题解

1.2.1、转化为求左右子树的最小值，如果左右子树最小值都大于根节点的值取较小的值。其他情况取左右子树较大的值。

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def findSecondMinimumValue(self, root: TreeNode) -> int: return self.findSecondMinimumValueT(root, root.val) def findSecondMinimumValueT(self, root: TreeNode, val: int) -> int: if not root: return -1 if root.val > val: return root.val l = self.findSecondMinimumValueT(root.left, val) r = self.findSecondMinimumValueT(root.right, val) if l > val and r > val: return min(l, r) return max(l, r)

二、230. 二叉搜索树中第K小的元素

2.1、题目描述

2.2、题解

2.2.1、二叉搜索树中序遍历是升序

class Solution: def kthSmallest(self, root: TreeNode, k: int) -> int: self.inorder(root) return self.list[k-1] def __init__(self) -> None: self.list = [] def inorder(self, root: TreeNode) -> None: if root.left: self.inorder(root.left) self.list.append(root.val) if root.right: self.inorder(root.right) # 优化，空间O(1) class Solution: def kthSmallest(self, root: TreeNode, k: int) -> int: self.inorder(root, k) return self.val def __init__(self) -> None: self.count = 0 self.val = 0 def inorder(self, root: TreeNode, k: int) -> None: if root.left: self.inorder(root.left, k) self.count += 1 if self.count == k: self.val = root.val if root.right: self.inorder(root.right, k)

2.2.2、迭代

class Solution: def kthSmallest(self, root: TreeNode, k: int) -> int: nodeStack = [] ans = None count = 0 cur = root while cur or nodeStack: if cur: nodeStack.append(cur) cur = cur.left else: node = nodeStack.pop() count += 1 if count == k: ans = node.val break cur = node.right return ans