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

中等

题目描述

解法：中序遍历

Java

class Solution {
    int num = 0;
	int res;
	public int kthSmallest(TreeNode root, int k) {
		if(root.left != null) {
			kthSmallest(root.left, k);
		}
		num++;
		if(num == k) res = root.val;
		if(root.right != null) {
			kthSmallest(root.right, k);
		}
		return res;
    }
}

Python

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        def dfs(root):
            if not root: return
            dfs(root.left)
            if self.k == 0: return
            self.k -= 1
            if self.k == 0: self.res = root.val
            dfs(root.right)

        self.k = k
        dfs(root)
        return self.res