二叉搜索树的第k个节点

二叉搜索树的第k个节点_牛客题霸_牛客网

问题简述

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

思路：中序遍历

• 定义全局变量 self.i，记录访问的节点编号；self.ret 记录答案，初始化为 -1；

• 当 self.i == k 时，更新 self.ret；

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