【题目链接】
python
# Definition for a binary tree node. class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None class Solution(object): def kthLargest(self, root, k): """ :type root: TreeNode :type k: int :rtype: int """ def dfs(root): # 终止条件:遇到叶子结点(None),则返回(由题中的定义而来) if not root: return # 递进过程1:右子树 dfs(root.right) # 因为需要求第K大的数,则应从右子树开始(二叉搜索树:左小右大) self.k -= 1 # 每遇到一个数,则k减一;直至减为0,即求得第k大的值 if self.k == 0: self.res = root.val # 递进过程2:左子树 dfs(root.left) self.k = k # 维护一个全局变量 dfs(root) return self.res