力扣: 二叉搜索树中第K小的元素

预备知识

二叉搜索树

• 它或者是一棵空树，或者是具有下列性质的二叉树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树。

中序遍历

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

二叉搜索树的中序遍历

二叉搜索树中，左子树的值 < 根节点 < 右子树，中序遍历顺序是 左 -> 根 -> 右，因此二叉搜索树的中序遍历结果为一串值从小到大递增序列。

题目: 二叉搜索树中第K小的元素

题目来源: 二叉搜索树中第K小的元素

题目描述: 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例：

输入： root = [3,1,4,null,2], k = 1
输出： 1
复制代码

题目分析

有了预备知识的基础，我们可以很轻易地得出当前题目的思路，使用中序遍历二叉搜索树，当遍历到第 k 个节点后，退出遍历，返回结果。

代码

本文章采取非递归模式的中序遍历.

def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
  cnt = 0
  p = root
  stack = []
  # 
  while p != None or len(stack) :
      # 遍历左子树
      while p != None:
          stack.append(p)
          p = p.left
      # 如果栈中不空，说明还存在节点待遍历
      if len(stack):
          tmp = stack.pop()
          # 中序遍历的右节点
          p = tmp.right
          cnt += 1
          # 遍历到第k个节点，返回结果
          if cnt == k:
              return tmp.val
复制代码

往期精彩文章

• 牛客最新前端JS笔试百题
• 抓取牛客最新前端面试题五百道 数据分析JS面试热点
• 原生JavaScript灵魂拷问(二)，你能全部答对吗？
• 原生JavaScript灵魂拷问(一)，你能答上多少？
• JavaScript之彻底理解原型与原型链
• JavaScript之预编译学习
• JavaScript之彻底理解EventLoop
• 《2w字大章 38道面试题》彻底理清JS中this指向问题

后语

如果大家感觉此文对你有一些帮助，希望能点个赞，鼓励鼓励阿包，阿包会不断努力的。另外如果本文章有问题，或者对文章其中一部分不理解，都可以评论区回复我，我们来一起讨论，共同学习，一起进步！