leetcode 230. kth-smallest-element-in-a-bst 二叉搜索树中第K小的元素 python3

时间：2021-1-28

题目地址：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

题目难度：Medium

题目描述：

给定一个二叉搜索树，编写一个函数 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 函数？

思路1：次等做法

利用二叉搜索树BST的特性：中序遍历是排好序的

直接找到中序排序到数组，返回index为k-1的即可

代码段1：通过

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        inorder = []
        def traverse(root):
            if root == None:
                return None
            traverse(root.left)
            inorder.append(root.val)
            traverse(root.right)
        traverse(root)
        return inorder[k - 1] 

总结：

1. 这是保底做法，中序遍历
2. 类变量踩过好几次坑了，原来可变变量修改全局时不需要增加global。

思路2：中等做法

还是利用二叉搜索树BST的特性：中序遍历是排好序的

但 不需要输出数组，顺序找到第k个即可退出

代码段2：通过

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution: 
    def traverse(self, root, k):
        if root == None:
            return None
        self.traverse(root.left, k)
        self.temp += 1
        if self.temp == k:
            self.res = root.val
            return 
        self.traverse(root.right, k)
    def kthSmallest(self, root: TreeNode, k: int) -> int: 
        self.temp = 0
        self.res = 0
        self.traverse(root, k)
        return self.res

总结：

1. 到k就退出来着，这里用了一个对象的成员变量。整了快1h。见这里的博客整理。
2. 更高级的是TreeNode增加一个size属性，代表该节点为根的树的节点总数，这样查找时能够讲到对数级。leetcode不支持那就到此为止了先。