题解 | #Tree# #二叉搜索树的第k个节点#

#coding:utf-8
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param proot TreeNode类 
# @param k int整型 
# @return int整型
#
class Solution:
    def __init__(self):
        #记录返回的节点
        self.res = None
        #记录遍历了多少个
        self.count = 0
        self.path = []

    def KthNode(self , proot , k ):
        # write code here
        #step 1：设置全局变量count记录遍历了多少个节点，res记录第k个节点。
        #step 2：另写一函数进行递归中序遍历，当节点为空或者超过k时，结束递归，返回。
        #step 3：优先访问左子树，再访问根节点，访问时统计数字，等于k则找到。
        #step 4：最后访问右子树。
        self.inOrder(proot, k)
        print ("Path: ", self.path)
        if self.res != None:
            return self.res.val 
        else:
            return -1


    def inOrder(self, root, k):
        if root == None:
            return
        if self.count > k:
            return 
        self.inOrder(root.left, k)
        self.count +=1
        #只记录第k个
        self.path.append(root.val)
        if self.count == k:
            self.res = root
        self.inOrder(root.right, k)