230 Kth Smallest element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

solution

# 如果k作为参数传值，k -=1 并判断k == 0有问题，还是因为k本身是immutable
class Solution:
    def __init__(self):
        self.rank = 0
        self.res = 0
    
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:          
        self.dfs(root, k)
        return self.res
    
    def dfs(self, root, k):
        if not root:
            return         
        
        self.dfs(root.left, k)
        
        self.rank += 1
        if self.rank == k:
            self.res = root.val
            return   

        self.dfs(root.right, k)

• 注意递归过程中的返回值

class Solution:
    def __init__(self):
        self.res = []

    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.dfs(root, k)
        return self.res[-1]

    def dfs(self, root, k):
        if not root:
            return

        self.dfs(root.left, k)

        if len(self.res) == k:
            return
        self.res.append(root.val)
        
        self.dfs(root.right, k)

时间复杂度：O(n) 空间复杂度：O()