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

2021/11/14 23:41:23

本文主要是介绍【LeetCode 二叉树专项】二叉搜索树中第 K 小的元素(230),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

    • 1. 题目
      • 1.1 示例
      • 1.2 说明
      • 1.3 限制
      • 1.4 进阶
    • 2. 解法一(递归中序遍历)
      • 2.1 分析
      • 2.2 实现
      • 2.3 复杂度

1. 题目

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

1.1 示例

  • 示例 1 1 1 :

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

在这里插入图片描述

  • 示例 2 2 2 :

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

在这里插入图片描述

1.2 说明

  • 来源: 力扣(LeetCode)
  • 链接: https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst

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)


这篇关于【LeetCode 二叉树专项】二叉搜索树中第 K 小的元素(230)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程