传送门：230. 二叉搜索树中第K小的元素。
给定一个二叉搜索树，编写一个函数
kthSmallest来查找其中第 k 个最小的元素。说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。示例 1:
输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 1示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 输出: 3进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化kthSmallest函数？
解法1：不使用辅助函数的递归“中序遍历”
Python 代码：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.counter = 0
self.res = 0
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
# 使用递归的方法，中序遍历
if root.left:
# 不是空，才继续遍历
self.kthSmallest(root.left, k)
self.counter += 1
# print(root.val)
if self.counter == k:
# 注意：千万不能在这里返回，后序遍历还要继续进行下去
self.res = root.val
# 注意：这里不能加 return
if root.right:
self.kthSmallest(root.right, k)
return self.res
if __name__ == '__main__':
node3 = TreeNode(3)
node1 = TreeNode(1)
node4 = TreeNode(4)
node2 = TreeNode(2)
node3.left = node1
node3.right = node4
node1.right = node2
solution = Solution()
result = solution.kthSmallest(node3, k=1)
print(result)
下面是另一种写法：使用 global 关键字、还要使用辅助函数：
Python 代码：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def kthSmallest(self, root, k):
global counter, res
counter = 0
res = 0
def dfs(root, k):
if not root:
# 如果是空，直接退出
return
dfs(root.left, k)
global counter, res
counter += 1
if counter == k:
res = root.val
dfs(root.right, k)
dfs(root, k)
return res
解法2：模拟系统栈的方式，即使用二叉树非递归遍历的通用方法
类似的方法还可以用于解决 LeetCode 第 144 题、第 94 题、第 145 题。
Python 代码：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 模拟系统栈的方式实现，是一种比较通用的做法，
# 可以作为二叉树的三种非递归遍历
def kthSmallest(self, root, k):
# 0 表示当前遍历到它，1 表示压入栈
# 刚开始是 1 ，不要写成 0 了
stack = [(1, root)]
while stack:
command, node = stack.pop()
if node is None:
# 不能写 return ，这不是递归
continue
if command == 0:
k -= 1
if k == 0:
return node.val
else:
# 此时 command == 1 的时候，表示递归遍历到的
# 注意：写的时候倒过来写
stack.append((1, node.right))
stack.append((0, node))
stack.append((1, node.left))
其实入栈的时候，就可以判断，我们只将非空结点入栈，推荐下面这种写法：
Python 代码：
class Solution:
def kthSmallest(self, root, k):
stack = [(1, root)]
while stack:
command, node = stack.pop()
if command == 0:
k -= 1
if k == 0:
return node.val
else:
# 模拟系统栈实现中序遍历(先左边、再自己、再右边)
# 注意：写的时候倒过来写
if node.right:
stack.append((1, node.right))
stack.append((0, node))
if node.left:
stack.append((1, node.left))
参考资料：https://blog.csdn.net/happyaaaaaaaaaaa/article/details/51487999
（本节完）
网友评论