一、题目

给定一个二叉搜索树的根节点

root

，和一个整数

k

，请你设计一个算法查找其中第

k



个最小元素（从 1 开始计数）。

二、解题思路

因为二叉搜索树的中序遍历是升序的，因此在中序遍历时记录访问节点的下标，当节点下标=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 {
    int idx=0;//记录第i个节点
	int ans=0;//记录要查找的数
	public int kthSmallest(TreeNode root, int k) {
		inOrder(root,k);
		return ans;
	}
	//二叉树的中序遍历
	public void inOrder(TreeNode root, int k) {
		if(root==null) {
			return ;
		}
		inOrder(root.left,k);
		//访问一个节点时，则将下标idx+1
		if(++idx==k) {
			//当idx==k时，则为题目需要查找的数
			ans=root.val;
		}
		inOrder(root.right,k);
		
	}
}

四、运行结果