LeetCode--HOT100题（44）

题目描述：230. 二叉搜索树中第K小的元素（中等）

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

LeetCode做题链接：LeetCode-两数之和

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

提示：

树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104

进阶： 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

题目接口

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
    
    }
}

解题思路

创建一个ArrayList用于存储中序遍历的结果。中序遍历是一种二叉树的遍历方式，顺序为左子树-根节点-右子树。这种遍历方式可以得到一个升序的序列。
定义一个方法kthSmallest，输入参数为二叉树的根节点和整数k，返回二叉树中第k小的元素。在这个方法中，首先调用dfs方法对二叉树进行中序遍历，将结果存储在list中。然后返回list中第k-1个元素，因为数组下标从0开始，而题目要求的k是从1开始的。
定义一个方法dfs，输入参数为二叉树的节点，递归地对该节点的左子树和右子树进行中序遍历。在这个方法中，首先判断当前节点是否为空，如果为空则直接返回。然后递归地对左子树进行中序遍历，将遍历得到的结果存储在list中。接着将当前节点的值添加到list中，最后递归地对右子树进行中序遍历。

通过这种方式，我们可以在O(n)的时间复杂度内找到二叉搜索树中第k小的元素，其中n是二叉树的节点数。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 创建一个ArrayList用于存储中序遍历的结果
	ArrayList<Integer> list = new ArrayList<>();
	
	// 定义一个方法，输入参数为二叉树的根节点和整数k，返回二叉树中第k小的元素
	public int kthSmallest(TreeNode root, int k) {
	    // 先对二叉树进行中序遍历，将结果存储在list中
	    dfs(root);
	    // 返回list中第k-1个元素，因为数组下标从0开始，而题目要求的k是从1开始的
	    return list.get(k - 1);
	}
	
	// 定义一个方法，输入参数为二叉树的节点，递归地对该节点的左子树和右子树进行中序遍历
	public void dfs(TreeNode root) {
	    // 如果当前节点为空，直接返回
	    if (root == null) {
	        return;
	    }
	    // 递归地对左子树进行中序遍历
	    dfs(root.left);
	    // 将当前节点的值添加到list中
	    list.add(root.val);
	    // 递归地对右子树进行中序遍历
	    dfs(root.right);
	}
}