【LeetCode 二叉树专项】二叉搜索树中第 K 小的元素(230)

文章目录

1. 题目

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

1.1 示例

  • 示例 1 1 1 :

    • 输入: root = [3, 1, 4, null, 2]k = 1
    • 输出: 1 1 1

【LeetCode 二叉树专项】二叉搜索树中第 K 小的元素(230)

  • 示例 2 2 2 :

    • 输入: root = [5, 3, 6, 2, 4, null, null, 1], k = 3
    • 输出: 3 3 3

【LeetCode 二叉树专项】二叉搜索树中第 K 小的元素(230)

1.2 说明

1.3 限制

  • 树中的节点数为 n n n ;
  • 1 ≤ k ≤ n ≤ 1 0 4 1 \le k \le n \le 10^4 1≤k≤n≤104 ;
  • 0 ≤ N o d e . v a l ≤ 1 0 4 0 \le Node.val \le 10^4 0≤Node.val≤104 。

1.4 进阶

如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化算法?

2. 解法一(递归中序遍历)

2.1 分析

实际上,由于题目指出这里给定的是一棵二叉搜索树,而由【数据结构Python描述】二叉搜索树简介与使用二叉搜索树实现有序映射可知,二叉搜索树有一个特殊的性质,即其中序遍历的结果是一个有序的递增序列,利用此性质可以方便地给出如下递归解法:

2.2 实现

from typing import Optional, List


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


class Solution:
    def _kth_smallest(self, root: Optional[TreeNode], tree: List[int]):
        if not root:
            return
        self._kth_smallest(root.left, tree)
        tree.append(root.val)
        self._kth_smallest(root.right, tree)

    def kth_smallest(self, root: Optional[TreeNode], k: int) -> Optional[int]:
        tree = []
        self._kth_smallest(root, tree)
        print(tree)
        return tree[k - 1]


def main():
    node6 = TreeNode(1)
    node5 = TreeNode(4)
    node4 = TreeNode(2, left=node6)
    node3 = TreeNode(6)
    node2 = TreeNode(3, left=node4, right=node5)
    node1 = TreeNode(5, left=node2, right=node3)
    root = node1
    sln = Solution()
    print(sln.kth_smallest(root, 3))  # 3


if __name__ == '__main__':
    main()

2.3 复杂度

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)
上一篇:[230]二叉搜索树中第K小的元素


下一篇:php把数组元素是字符串的数字转换为int类型的数组