二叉搜索树中第 K 小的元素

原题链接

使用的方法

递归

解题思路

• 二叉搜索树（BST）是指对于树中的每个节点，左子树中的所有节点值都小于该节点的值，右子树中的所有节点值都大于该节点的值，并且左右子树也必须是二叉搜索树。
• 要找到二叉搜索树中第 K 小的元素，我们可以利用二叉搜索树的性质进行中序遍历。中序遍历会按照从小到大的顺序访问节点。
• 我们可以在中序遍历的过程中维护一个计数器，当访问到第 K 个节点时，记录下该节点的值并返回。
• 递归的终止条件是当节点为 null 时，返回。我们首先递归访问左子树，然后访问当前节点，最后递归访问右子树。
• 在访问当前节点时，我们先递减 K 的值，如果 K 的值变为 0，说明当前节点就是第 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 res;
    int k;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    public void dfs(TreeNode node){
        if(node == null)
            return;
        dfs(node.left);
        if(k == 0)
            return;
        if(--k == 0)
            res = node.val;
        dfs(node.right);
    }
}