二叉搜索树 230. 二叉搜索树中第K小的元素 1038. 从二叉搜索树到更大和树

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

解题思路：

1. 二叉搜索树的中序遍历，是节点的升序顺序，这也是二叉搜索树的特性。
2. 设置一个值，来记录遍历的层数是否为 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. 从二叉搜索树到更大和树

解题思路：

1. 还是利用二叉搜索树中序遍历的特性， 但中序遍历是先遍历左子树，我们没办法算出大于等于当前节点的累加和。
2. 所以颠倒一下左右子树的先后遍历顺序。

# 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) # 先遍历右子树
        
        self.res += root.val

        root.val = self.res

        self.traverse(root.left)