[数据结构与算法]剑指offer面试题54：二叉搜索树的第k大节点（golang实现）

题目描述

给定一棵二叉搜索树，请找出其中第k大的节点。

示例1

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

示例2

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

提示

1 ≤ k ≤ 二叉搜索树元素个数

Leetcode链接：剑指offer面试题54：二叉搜索树的第k大节点

算法分析

按照右中左的顺序遍历二叉搜索树即可得到节点的递减排列，用数组保存后返回第k大数即可。

复杂度分析

问题规模为二叉树的节点个数n

• 时间复杂度：O($n$)，k等于n或者二叉树退化为链表时需要遍历完整个二叉树。
• 空间复杂度：O($n$)，最坏情况下需要保存二叉树的所有节点

Golang代码如下

func inOrder(node *TreeNode) []int {
	in := make([]int, 0)
	if node != nil {
		in = append(in, inOrder(node.Right)...)
		in = append(in, node.Val)
		in = append(in, inOrder(node.Left)...)
	}
	return in
}

func kthLargest(root *TreeNode, k int) int {
	arr := inOrder(root)
	return arr[k-1]
}