# 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# 解法1：暴力法，直接遍历整棵树，然后在数组中依次弹出最小值即可
# 这样写，在我自己的机器上是没问题的，但是，网站上通不过，而且每次运行的结果还都不同，不知道是不是因为网站用的python2的原因
class Solution:
    def __init__(self):
        self.sol = []

    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        self.get_level(pRoot)
        temp = None
        self.sol.sort()
        if k > 0:
            temp = self.sol[k - 1]

        return temp

    def get_level(self, my_root):
        if not my_root:
            return None
        else:
            self.sol.append(my_root.val)
            self.get_level(my_root.left)
            self.get_level(my_root.right)


# 解法2：其实，就按照中序遍历就肯定是从小到大排列了
class Solution1:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        # 第三个节点是4
        # 前序遍历5324768
        # 中序遍历2345678
        # 后序遍历2436875
        # 所以是中序遍历，左根右
        global result
        result = []
        self.midnode(pRoot)
        if k <= 0 or len(result) < k:
            return None
        else:
            return result[k - 1]

    def midnode(self, root):
        if not root:
            return None
        self.midnode(root.left)
        result.append(root)
        self.midnode(root.right)


node1 = TreeNode(8)
node2 = TreeNode(6)
node3 = TreeNode(10)
node4 = TreeNode(5)
node5 = TreeNode(7)
node6 = TreeNode(9)
node7 = TreeNode(11)

node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7

my_sol = Solution()
print(my_sol.KthNode(node1, 1))