题目
给定一棵二叉搜索树,请找出其中第k大的节点。
示例:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4
python代码
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
def inorder(node):
if not node:
return
inorder(node.left)
self.outlist.append(node.val)
inorder(node.right)
self.outlist = []
inorder(root)
return self.outlist[-k]
其实,如果知道了“二叉树搜索树的中序遍历就是一个递增数组”,那这道题就很好解决,上述的代码也是先获得二叉树搜索树的中序遍历,直接取低k大个值即可。
思考
为什么搜索二叉树的中序遍历是一个递增数组?思考中序遍历的顺序:左-中-右,而搜索二叉树中值大小的关系是右>中>左,所以中序遍历正好是按照从小到大的顺序遍历。