LeetCode 230. 二叉搜索树中第K小的元素（遍历树 + 二分搜索）

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

example.jpg

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
说明：倒数为 1、2、3、4、5、6，第3小的为3。

这道题没有注意二叉搜索树，直接遍历全部节点并维护最小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: Optional[TreeNode], k: int) -> int:
        # 把所有最小的数记录下来
        target = [10001] * k

        def dfs(node, target):
            # 使用二分法搜索在哪两个数中间
            # print('dfs:', node.val, target)
            bi_search(node.val, target)
            # print('bi_search:', target)
            
            if node.left:
                dfs(node.left, target)

            if node.right:
                dfs(node.right, target)


        def bi_search(val, nums):
            l = 0
            r = k-1

            # print(l, r)
            while l < r-1:
                mid = (l + r) // 2
                if nums[mid] > val:
                    r = mid
                elif nums[mid] < val:
                    l = mid
                else:
                    l = r = mid

                # print('while:',l, r)

            # print(l, r)
            if val <= nums[l]:
                nums.insert(l, val)
                del nums[-1]
            elif val <= nums[r]:
                nums.insert(r, val)
                del nums[-1]

        # bi_search(3, [10001, 10001, 10001, 10001])
        dfs(root, target)
        # print(target)
        return target[-1]