230. 二叉搜索树中第K小的元素 [medium]

https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

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

通过次数60,560 | 提交次数85,068

First Try

2020-07-21

中序遍历的写法，感觉有点拧巴。

要不是知道二叉搜索树和中序遍历的关系，这题可能还写不出来。

看了一些题解，如果要频繁查找k的值，需要修改树的结构，在节点实时添加排序。

# 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:

        count = {"c": 0, "rv": None}
        def inorder_dfs(root):
            if not root:
                return root 
            inorder_dfs(root.left)
            count["c"] += 1
            if count["c"] == k:
                count['rv'] = root.val 
                return  
            inorder_dfs(root.right)
        
        inorder_dfs(root)

        return count['rv']

执行用时：88 ms, 在所有 Python3 提交中击败了9.47%的用户
内存消耗：17.7 MB, 在所有 Python3 提交中击败了7.14%的用户

原始inorder中序遍历

没有中途终止，结果速度还更快，搞笑咯。

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        
        def inorder(root):
            return inorder(root.left) + [root.val] + inorder(root.right) if root else []
        return inorder(root)[k-1]

执行用时：68 ms, 在所有 Python3 提交中击败了58.71%的用户
内存消耗：17.8 MB, 在所有 Python3 提交中击败了7.14%的用户

230. 二叉搜索树中第K小的元素 [medium]​

First Try​

230. 二叉搜索树中第K小的元素 [medium]

First Try