（Java）leetcode-230 Kth Smallest Element in a BST

ゝ一世哀愁。 2023-06-15 06:45 30阅读 0赞

# 题目描述 #

【二叉搜索树中第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 函数？

# 思路 #

二叉搜索树（二叉查找树、二叉排序树、BST）的**中序遍历**就是其所有节点的val按照升序排列。这样根据中序遍历，每找到一个元素判断他是否是第k个元素即可。

# 代码 #

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        private int i = 0;
        private int val = 0;
    
        public int kthSmallest(TreeNode root, int k) { 
            inorder(root, k);
            return val;
        }
    
        public void inorder(TreeNode root, int k) { 
            if (root == null) { 
                return;
            }
            inorder(root.left, k);
            if (k == ++i) { 
                val = root.val;
                return; //只能省略第k小的结点的右子树的遍历（如果有右子树的话）
            }
            inorder(root.right, k);
        }
    }