M-230. Kth Smallest Element in a BST

Loading...LeetCode

# 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
# O(N), O(N)
# 直接中序遍历排序，找k（下面写错了，不应该是preorder）
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def preorder(root, res):
            if root!=None:
                preorder(root.left, res)
                res.append(root.val)
                preorder(root.right, res)
        res = []
        preorder(root, res)
        return res[k-1]

# 如果insert/delete很频繁，即经常修改树，那么可以拿一个deque来存对应的
# treenode, 这样添加或者删除节点也只是O(H)，查找k也只是O(k).
from collections import deque
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def preorder(root, res):
            if root!=None:
                preorder(root.left, res)
                res.append(root)
                preorder(root.right, res)
        res = deque([])
        preorder(root, res)
        return res[k-1].val