230. Kth Smallest Element in a BST
My solution:
python
# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
# inorder
order = []
def dfs(root):
if not root:
return
dfs(root.left)
order.append(root.val)
dfs(root.right)
dfs(root)
print(order)
return order[k-1]My solution 2:
python
# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
# inorder
cnt = 0
ans = 0
def dfs(root):
if not root:
return
dfs(root.left)
nonlocal cnt
cnt += 1
if cnt == k:
nonlocal ans
ans = root.val
dfs(root.right)
dfs(root)
return ans写法一使用了一个外部变量记录答案，能否不使用外部变量记录呢？
可以，做法如下：
-
递归边界：如果当前节点是空节点，返回 −1，表示没有找到。注意题目保证节点值非负。
-
执行中序遍历，先递归左子树。
-
判断左子树的返回值 leftRes 是否为 −1。如果不是 −1，说明我们在左子树中找到了答案，返回 leftRes。如果是 −1，说明尚未找到答案，继续下一步。
-
把 k 减少 1。如果 k=0，那么答案就是当前节点值，返回当前节点值。
-
现在，答案要么在当前节点的右子树中，要么在除了当前子树的其余节点中。递归右子树，如果答案在右子树中，那么直接返回答案；如果答案不在右子树中，那么右子树也会返回 −1，由于当前子树搜索完毕，所以当前子树没有找到答案，返回 −1。综上所述，可以直接返回右子树的返回值。
python
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
def dfs(node: Optional[TreeNode]) -> int:
if node is None:
return -1 # 题目保证节点值非负，用 -1 表示没有找到
left_res = dfs(node.left)
if left_res != -1: # 答案在左子树中
return left_res
nonlocal k
k -= 1
if k == 0: # 答案就是当前节点
return node.val
return dfs(node.right) # 右子树会返回答案或者 -1
return dfs(root)
作者：灵茶山艾府
链接：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/solutions/2952810/zhong-xu-bian-li-pythonjavaccgojsrust-by-wc02/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。