> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2022/03/niu-ke-0081-zhong-deng-er-cha-sou-suo-shu-de-dikge-jie-dian.md).

# 二叉搜索树的第k个节点

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/03/pages/R5NyOzkn3qAZy7wCx1pS#中等) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/03/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E4%BA%8C%E5%8F%89%E6%A0%91/%E6%A0%91\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/03/pages/R5NyOzkn3qAZy7wCx1pS#二叉树树)

> [二叉搜索树的第k个节点\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/57aa0bab91884a10b5136ca2c087f8ff)

**问题简述**

```
给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。
1.返回第k小的节点值即可
2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
3.保证n个节点的值不一样
```

**思路：中序遍历**

* 定义全局变量 `self.i`，记录访问的节点编号；`self.ret` 记录答案，初始化为 `-1`；
* 当 `self.i == k` 时，更新 `self.ret`；

<details>

<summary><strong>Python</strong></summary>

```python
class Solution:
    def KthNode(self , root: TreeNode, k: int) -> int:
        if not root: return -1
        
        self.i = 0
        self.ret = -1
        
        def dfs(x):
            if not x: return
            
            dfs(x.left)
            self.i += 1
            if self.i == k:
                self.ret = x.val
                return
            dfs(x.right)
        
        dfs(root)
        return self.ret
```

</details>