LeetCode热题100--230. 二叉搜索树中第 K 小的元素--中等

1. 题目

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

示例 1：

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

示例 2：

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

2. 题解

/**
 * 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, k;
    void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        if (k == 0) return;
        if (--k == 0) res = root.val;
        dfs(root.right);
    }
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
}

3. 解析

出自：230. 二叉搜索树中第 K 小的元素（中序遍历，清晰图解）

1. 1-4行：这是对TreeNode类的定义或者说结构体的定义。它是一棵二叉树，其中每个节点最多有两个子节点，一个左子节点和一个右子节点。如果没有提供值、左子节点或右子节点，它们将默认为null。

2. 7-12行：这些代码定义了一个名为Solution的类，其中包含了一些与二叉树相关的方法。这段代码的主要功能是找到BST中第k小的元素。

3. 14-20行：在dfs(root)方法中，我们使用深度优先搜索遍历来寻找第k小的元素。如果当前节点为null，则返回；否则，递归调用左子树和右子树的dfs函数。

4. 21-24行：在执行这段代码之前，需要将实例变量res和k初始化。res用于存储第k小的元素，而k是我们想要找到的排名。

5. 30-35行：定义了kthSmallest(TreeNode root, int k)函数。该函数接受根节点和要找的第k小的元素作为参数。它首先将实例变量res和k初始化为输入参数，然后调用dfs方法开始搜索并返回结果。

6. 在这段代码中，我们使用了深度优先搜索（DFS）的方法来遍历二叉树。每次访问一个节点时，如果它是第k小的元素，那么就把它的值赋给res变量。这样，当所有的节点都被访问完毕后，res将保存我们要找的第k小的元素。