LeetCode0230: 二叉搜索树中第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 函数？

解题思路：

递归算法的关键是要明确函数的「定义」是什么，然后相信这个定义，利用这个定义推导最终结果。

写树相关的算法，简单说就是，先搞清楚当前 root 节点该做什么，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。

二叉树题目的一个难点在于如何通过题目的要求思考出每一个节点需要做什么

二叉树解题策略

一 递归 二 队列 + 迭代 （层次遍历） 三 栈 + 迭代 （非递归遍历） 四 其它

三种基本的遍历方式，都可以用递归来实现。写递归算法的时候，需要注意递归退出条件以及递归操作的表达。

二叉树的中序遍历会得到一个递增序列

自己的解法实现

self.num = 0
        self.res = 0
        def dfs(node, k):
            flag = False
            if not node: return False
            flag = dfs(node.left, k)

            if flag: return True
            self.num += 1
            if self.num == k:
                self.res = node.val
                return True
            flag = dfs(node.right, k)
            return flag
        dfs(root, k)
        return self.res

网上比较优秀的解法

解法一

方法一：递归 算法： 通过构造 BST 的中序遍历序列，则第 k-1 个元素就是第 k 小的元素。

def kthSmallest2(self, root, k):
        def inorder(node):
            return inorder(node.left) + [node.val] + inorder(node.right) if node else []
        return inorder(root)[k - 1]

解法二

方法二：迭代 算法： 在栈的帮助下，可以将方法一的递归转换为迭代，这样可以加快速度，因为这样可以不用遍历整个树，可以在找到答案后停止。

def kthSmallest3(self, root, k):
        stack = []
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if not k:
                return root.val
            root = root.right

解法三

二叉搜索树的中序遍历是递增序列

def kthSmallest4(self, root, k):
        self.num = 0
        self.res = 0
        def dfs(node):
            if not node:return
            dfs(node.left)
            self.num += 1
            if self.num == k:
                self.res = node.val
                return
            dfs(node.right)

        dfs(root)
        return self.res

相关知识总结和思考

相关知识：

BFS：广度/宽度优先。其实就是从上到下，先把每一层遍历完之后再遍历一下一层。

可以使用Queue的数据结构。我们将root节点初始化进队列，通过消耗尾部，插入头部的方式来完成BFS。

二叉搜索树（BST）的特性：

1. 若它的左子树不为空，则所有左子树上的值均小于其根节点的值
2. 若它的右子树不为空，则所有右子树上的值均大于其根节点的值
3. 它的左右子树也分别为二叉搜索树

递归与迭代的区别

递归：重复调用函数自身实现循环称为递归； 迭代：利用变量的原值推出新值称为迭代，或者说迭代是函数内某段代码实现循环；