给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1:输入: root = [3,1,4,null,2], k = 13/ \1 4\2
输出: 4
示例 2:输入: root = [5,3,6,2,4,null,null,1], k = 35/ \3 6/ \2 4/1
输出: 4
1、题目分析
首先明白什么是二叉搜索树，这个树的特点就是每个节点的左子树小于根节点，右子树都是大于根节点的。所以对这个树进行中序遍历就能得到已经从小到大排好序的数组。所以两个方法：1、中序遍历，取倒数第k个。2、右中左进行遍历，取到k个数。
2、解题分析
- O（1）
- 采用右中左遍历
- 如果取到倒数第k个元素就退出递归直接返回结果
- O（n）
- 将中序遍历的结果存放到数组中
- 取倒数第k个元素就可以了
3、代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def kthLargest(self, root: TreeNode, k: int) -> int:#O(1)def dfs(root):if not root: returndfs(root.right)if self.k == 0: returnself.k -= 1if self.k == 0: self.res = root.valdfs(root.left)self.k = kdfs(root)return self.res#O(n)if not root:return 0res = []i=1def helper(root):if not root:return 0helper(root.left)res.append(root.val)helper(root.right)helper(root)return res[-k]
总结：二叉搜索树是一个有序的树，采用中序遍历就可以得到一个顺序数组。