[NC]81. 二叉搜索树的第k个节点

🚩传送门：牛客题目

题目

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

示例 1:

输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 1

示例 2:

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

解题思路1：中序遍历

本文解法基于此性质：二叉搜索树的中序遍历为 递增序列 。

由上图可以知道，对于第K小，使用中序遍历，对于第k大，使用中序遍历倒序。
为求第k个节点，需要实现以下 三项工作 ：

• 递归遍历时计数，统计当前节点的序号；
• 递归到第k个节点时，应记录结果res ；
• 记录结果后，后续的遍历即失去意义，应提前终止（即返回）。

复杂度分析

时间复杂度：，其中 是二叉树结点个数。

  - 当树退化为链表时（全部为右子节点），无论`k`的值大小，递归深度都为`N`

空间复杂度：，使用的额外空间复杂度为常数。

  - 当树退化为链表时（全部为右子节点），系统使用 ![](https://cdn.nlark.com/yuque/__latex/7ba55e7c64a9405a0b39a1107e90ca94.svg#card=math&code=O%28n%29%20&height=23&id=b5nnN) 大小的栈空间。

官方代码

class Solution {
    int res, k;
    public int KthNode(TreeNode root, int k) {
        this.k = k;
        this.res =-1;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null||k<=0) return;
        dfs(root.left);
        if(--k == 0) res = root.val;
        dfs(root.right);
    }
}