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