LeetCode 第 230 题：二叉搜索树中第 K 小的元素

传送门：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

（本节完）