[剑指 Offer 第 2 版第 54 题] “二叉搜索树的第k个结点”做题记录

第 54 题：二叉搜索树的第 k 大结点

传送门：二叉搜索树的第 k 大结点，牛客网 online judge 地址。

给定一棵二叉搜索树，请找出其中的第 k 小的结点。

你可以假设树和 k 都存在，并且 1≤ k ≤ 树的总结点数。

样例：

输入：root = [2, 1, 3, null, null, null, null] ，k = 3

2 / \ 1 3

输出：3

思路：使用栈模拟 BST 的中序遍历。

Python 代码：

  class Solution(object):
        def kthNode(self, root, k):
            """
            :type root: TreeNode
            :type k: int
            :rtype: TreeNode
            """

            if root is None:
                return None

            # 1 表示递归处理，0 表示当前我就要处理这个结点
            stack = [(1, root)]

            while stack:
                type, node = stack.pop()
                if type == 0:
                    k -= 1
                    if k == 0:
                        return node
                else:
                    if node.right:
                        stack.append((1, node.right))
                    stack.append((0, node))
                    if node.left:
                        stack.append((1, node.left))

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/