LeetCode 230. 二叉搜索树中第K小的元素（中序 + 栈）

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

example.jpg

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
说明：倒数为 1、2、3、4、5、6，第3小的为3。

之前一直觉得中序遍历搜索绕，主要原因是其中有1个栈。
另外由于递归也是栈，可以使用递归来做，更加清晰一些，但是递归需要判断结束，满足条件后不能继续递归。

栈

# 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:

    # 二叉搜索树具有如下性质：
    # 结点的左子树只包含小于当前结点的数。（节点的整个左子树都小于节点）
    # 结点的右子树只包含大于当前结点的数。
    # 所有左子树和右子树自身必须也是二叉搜索树。

        # 中序遍历搜索
        stack = []
        
        node = root
        while node:
            while node.left:
                stack.append(node)
                node = node.left

            stack.append(node)

            while stack:
                node = stack.pop()
                k -= 1

                # print(node.val)

                if k == 0:
                    return node.val

                if node.right:
                    node = node.right
                    break

递归

# 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:

        # 二叉搜索树具有如下性质：
        # 结点的左子树只包含小于当前结点的数。（节点的整个左子树都小于节点）
        # 结点的右子树只包含大于当前结点的数。
        # 所有左子树和右子树自身必须也是二叉搜索树。

        find = [k]

        def search(node):
            if node.left:
                res = search(node.left)
                # 注意：不可以使用if res，因为res可能为0
                if not res is None:
                    return res
            
            find[0] -= 1
            if find[0] == 0:
                return node.val

            if node.right:
                res = search(node.right)
                if not res is None:
                    return res

        return search(root)