题解 | #二叉树之寻找第k大#

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

1. 和前面一道题【第k轻牛牛】类似，这里是求第k大，前面是求第k小，其实就是反过来
2. 中序遍历反过来可以得到树中元素的有序逆序序列,利用栈模拟逆序中序遍历的过程,就可以得到第K大的节点
3. 初始化栈,将根节点入栈，当栈不空时,遍历左子树并入栈，出栈一个节点并计数，当计数等于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 kthLargest(self , root: TreeNode, k: int) -> int:
        n = 0
        stack = []
        cur = root
  
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.right
      
            cur = stack.pop()
            n += 1
            if n == k:
                return cur.val
            cur = cur.left

        return -1