1.题目描述
2.思路
重点
在二叉搜索树中，任意子节点都满足“左子节点 < 根节点 < 右子节点”的规则。因此二叉搜索树具有一个重要性质：二叉搜索树的中序遍历为递增序列。
方法一：中序遍历
二叉搜索树具有如下性质：
结点的左子树只包含小于当前结点的数。
结点的右子树只包含大于当前结点的数。
所有左子树和右子树自身必须也是二叉搜索树。
二叉树的中序遍历即按照访问左子树——根结点——右子树的方式遍历二叉树；在访问其左子树和右子树时，我们也按照同样的方式遍历；直到遍历完整棵树。
方法二：
树的前序遍历 + 排序
先对二叉树进行一次完整遍历，将所有节点存入列表中，最后对列表排序后返回目标值。树的遍历可以使用 DFS 或 BFS。
3.代码实现
方法一：（中序）
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;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;}}
public class H230 {int result=-1;//用于记录第 k 小的节点值，初始为 -1（默认值）int cnt=0;//用于记录已经访问了多少个节点（从小到大）
public int kthSmallest(TreeNode root, int k) {inorder(root,k);// 从根节点开始中序遍历return result; // 返回第 k 小的值}
public void inorder(TreeNode root ,int k)
{if(root==null) return;//二叉搜索树中序遍历是有序的升序遍历 （左根右）
inorder(root.left,k);// 先递归左子树（较小的值
cnt++;//遍历当前节点，这个计数器就+1
if (cnt==k)// 如果当前是第 k 个访问的节点
{result= root.val;// 记录该节点值为结果return; // 提前返回，避免不必要的遍历。这句话不加也可以返回正确结果
}
inorder(root.right,k); // 最后递归右子树（较大的值）
}public static void main(String[] args){H230 test=new H230();TreeNode node1 = new TreeNode(1);TreeNode node3 = new TreeNode(3, node1, null);TreeNode node6 = new TreeNode(6);TreeNode node4 = new TreeNode(4, node3, node6);TreeNode node9 = new TreeNode(9);TreeNode node7 = new TreeNode(7, node4, node9);TreeNode node13 = new TreeNode(13);TreeNode node12 = new TreeNode(12, null, node13);TreeNode root = new TreeNode(10, node7, node12);int res=test.kthSmallest(root,2);System.out.print(res);}}方法二：(前序+排序）
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;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;}}
public class H230 {List<Integer> list=new ArrayList<>();//全局变量，值可以实时更新public int kthSmallest(TreeNode root, int k) {dfs(root);Collections.sort(list);return list.get(k-1);}void dfs(TreeNode root){if(root==null){return ;//因为这个dfs方法返回的是空}list.add(root.val);//在list中，每次添加当前根的值dfs(root.left);//递归遍历左子树dfs(root.right);//递归遍历右子树}public static void main(String[] args){H230 test=new H230();TreeNode node1 = new TreeNode(1);TreeNode node3 = new TreeNode(3, node1, null);TreeNode node6 = new TreeNode(6);TreeNode node4 = new TreeNode(4, node3, node6);TreeNode node9 = new TreeNode(9);TreeNode node7 = new TreeNode(7, node4, node9);TreeNode node13 = new TreeNode(13);TreeNode node12 = new TreeNode(12, null, node13);TreeNode root = new TreeNode(10, node7, node12);int res=test.kthSmallest(root,2)System.out.print(res);}}
