博客

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

230. 二叉搜索树中第K小的元素 – 力扣（Leetcode）

## 思路

二叉搜索树

二叉搜索树有一个非常重要的特性就是：

二叉搜索树的中序遍历结果一定是有序的

我们可以根据中序遍历，设置计数器，每经过一个结点计数器加一，达到第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 target = 0;
    int count = 0;
    int res;
public int kthSmallest(TreeNode root, int k) {
    res = k;
    inOrderTraversal(root);
    return target;
}
public void inOrderTraversal(TreeNode node) {
    if (node == null)
        return;
    //访问左子节点
    inOrderTraversal(node.left);
    //访问当前节点，如果访问到第k个就把target赋值
    count++;
    if (res == count) {
        target = node.val;
        return;
    }
    //访问右子节点
    inOrderTraversal(node.right);
}
}