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

题目

给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明

你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

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

示例 2:

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

进阶

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


实现

思路: 对二叉搜索树进行中序遍历,即可得到由小到大的序列。

  • 状态:通过
  • 91 / 91 个通过测试用例
  • 执行用时: 128 ms, 在所有 C# 提交中击败了 100.00% 的用户
  • 内存消耗: 27.2 MB, 在所有 C# 提交中击败了 9.09% 的用户
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
 
public class Solution 
{
    List<int> _lst;
    public int KthSmallest(TreeNode root, int k) 
    {
        _lst=new List<int>();
        MidTraver(root);
        return _lst[k-1];
    }
    
    private void MidTraver(TreeNode current)
    {
        if(current==null)
            return;
        MidTraver(current.left);
        _lst.Add(current.val);
        MidTraver(current.right);
    }
}
浙ICP备19012682号