剑指offer-python：52.二叉搜索树的第k大节点/第k小节点

题目：给定一棵二叉搜索树，请找出其中第K大/第k小的节点。

二叉搜索树：根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值，这一规则适用于二叉查找树中的每一个节点。

如图：

 思路：利用二叉搜索树特性，栈。

代码：

# class root_tree:
#     def f(self , root):
#         self.root = root
#         self.left = root.left
#         self.right = root.right

class Solution:
    def func_max(self , root , k):
        stack = []
        ans = root
        while stack or root:
            while root:
                stack.append(root)
                root = root.right
            root = stack.pop()
            k -= 1
            ans = root
            root = root.left
            if k == 0:
                return ans

    def func_min(self , root , k):
        stack = []
        res = root
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            res = root
            root = root.right
            if k == 0:
                return res