本文共 862 字，大约阅读时间需要 2 分钟。

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。

你可以假设树和k都存在，并且1≤k≤树的总结点数。

样例描述

输入：root = [2, 1, 3, null, null, null, null] ，k = 3    2   / \  1   3输出：3/** * Definition for a binary tree node. * public class TreeNode {    *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) {    val = x; } * } */

思路

1. 理清逻辑，第k小的结点实际上是结点单调增排序后的第k个。
2. BST(二叉搜索树)的特点是中序遍历序列是单调增序列。因此直接递归进行中序遍历，设置计数器c，当增加到k时结点就是答案。
3. dfs递归中要注意root!=null这个范围限制，不然会报空指针错误。

代码

class Solution {         TreeNode ans;      //计数器，加到k时就是所要求的      int c=0;    public TreeNode kthNode(TreeNode root, int k) {           dfs(root,k);        return ans;    }  //直接中序遍历即可，因为BST的中序遍历是单调增序列    void dfs(TreeNode root,int k){            if(root!=null){                dfs(root.left,k);             c++;             if(c==k) ans=new TreeNode(root.val);             dfs(root.right,k);         }         return;    }}