题解 | #第k轻的牛牛#

• 题目考察的知识点 : 二叉树的遍历
• 题目解答方法的文字分析：

1. 中序遍历可以得到树中元素的有序序列,利用栈模拟中序遍历的过程,可以高效地找到第k小的值。
2. 初始化栈,将根节点入栈，当栈不空时,遍历左子树并入栈，出栈一个节点并计数，当计数等于k时,返回节点值，继续遍历右子树

• 本题解析所用的编程语言：Python
• 完整且正确的编程代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param k int整型 
# @return int整型
#
class Solution:
    def kthLighest(self , root: TreeNode, k: int) -> int:
        n = 0
        stack = []
        cur = root
  
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
      
            cur = stack.pop()
            n += 1
            if n == k:
                return cur.val
            cur = cur.right

        return -1

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param k int整型 
# @return int整型
#
class Solution:
    def kthLighest(self , root: TreeNode, k: int) -> int:
        n = 0
        stack = []
        cur = root
  
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
      
            cur = stack.pop()
            n += 1
            if n == k:
                return cur.val
            cur = cur.right

        return -1