1. 首页
  2. 剑指offer经典面试题

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

[剑指 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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3299.html

« [剑指 Offer 第 2 版第 53 题] “在排序数组中查找数字”做题记录
[剑指 Offer 第 2 版第 56 题] “数字在排序数组中出现的次数”做题记录»

相关推荐

QR code