Binary search tree 230 The element with the smallest K in the binary search tree 1038 From binary search tree to larger sum tree

230. Binary search tree K Small elements

Their thinking ：

1. Middle order traversal of binary search tree , Is the ascending order of nodes , This is also the characteristic of binary search tree .
2. Set a value , To record whether the number of layers traversed is K.

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:

        self.count = 0
        self.res = 0
        self.traverse(root,k)
        return self.res
        

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

        self.traverse(root.left,k)

        self.count += 1
        if k == self.count:
            self.res = root.val
            return

        self.traverse(root.right,k)

1038. From binary search tree to larger sum tree

Their thinking ：

1. Or use the binary search tree in order to traverse the characteristics , But the middle order traversal first traverses the left subtree , We can't calculate the cumulative sum greater than or equal to the current node .
2. So reverse the traversal order of the left and right subtrees .

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        
        self.res = 0
        self.traverse(root)
        return root

    def traverse(self, root):
        if not root:
            return None

        self.traverse(root.right) #  First traverse the right subtree 
        
        self.res += root.val

        root.val = self.res

        self.traverse(root.left)