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

题目链接：230. 二叉搜索树中第K小的元素

题目描述

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

核心思考：理解二叉搜索树的中序遍历特性

本题考察二叉搜索树（BST）的核心性质。所有有效构造的二叉搜索树都默认符合一个绝对的基础定理：
即对其执行中序遍历（顺序为“左子节点 -> 根节点 -> 右子节点”），获得的结果数组必定为一个严格整体升序排布的递增一维数组。

据此我们可以整理出直观的步骤流：

1. 建立一个空列表 mid。
2. 定义传统的深度优先探寻函数 dfs。在中序环节对应的位置（即在遍历打探过左节点之后，继续打探右节点之前），将经过的每个节点追加存储至 mid 末端。
3. 从 root 一路遍历完毕。
4. 由于题目设定首位序号是以 1 出发开始查起的，直接使用数组切片返回位置在 k-1 下标所囊落保存节点本体内部的值属性 val 即可得到想要的极小项解答。

解题思路 (Python)

# 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:
        mid = []
        def dfs(node):
            if node == None:
                return
            dfs(node.left)
            mid.append(node)
            dfs(node.right)
        
        dfs(root)
        return mid[k-1].val

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是二叉搜索派发枝干下连带拥有的元素数规模。在这套实现代码逻辑里选择了打空到底铺底收集方案而不做提早减枝退结。
• 空间复杂度：$O(N)$。采用空间换形式挂坠将整个中序节点顺序重影克隆存储入了附加 mid 队列，叠加调用回调占坑递归也共享这一档位上限。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

val1 val2 val3 ... valN

输入一行整数数组表示二叉树的层序遍历，None 表示空节点。

完整代码：

import sys

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(arr):
    if not arr or arr[0] is None:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    i = 1
    while queue and i < len(arr):
        node = queue.pop(0)
        if arr[i] is not None:
            node.left = TreeNode(arr[i])
            queue.append(node.left)
        i += 1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            queue.append(node.right)
        i += 1
    return root

def tree_to_list(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    while result and result[-1] is None:
        result.pop()
    return result

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
    mid = []
            def dfs(node):
                if node == None:
                    return
                dfs(node.left)
                mid.append(node)
                dfs(node.right)

            dfs(root)
            return mid[k-1].val

def main():
    arr = sys.stdin.read().strip().split()
    tree_arr = [None if v == 'None' else int(v) for v in arr]
    root = build_tree(tree_arr)

    sol = Solution()
    result = sol.kthSmallest(root)
    print(result)

if __name__ == "__main__":
    main()