剑指 Offer 54. 二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第 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
限制：
原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 6.3 MB, 提交时间: 2021-03-19 23:32:50
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthLargest(root *TreeNode, k int) int {
count := make([]int, 1)
visit(root, &count)
return count[len(count)-k]
}
func visit(node *TreeNode, count *[]int) {
if node.Left != nil {
visit(node.Left, count)
}
if node != nil {
*count = append(*count, node.Val)
}
if node.Right != nil {
visit(node.Right, count)
}
}
python3 解法, 执行用时: 80 ms, 内存消耗: 18.5 MB, 提交时间: 2021-03-17 22:37:18
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
# 二叉搜索树的中序遍历就是有序的
rs = self.visit(root, [])
return rs[-k]
def visit(self, node: TreeNode, rs: list):
if node is None:
return rs
if node.left:
self.visit(node.left, rs)
rs.append(node.val)
if node.right:
self.visit(node.right, rs)
return rs
python3 解法, 执行用时: 72 ms, 内存消耗: 18.5 MB, 提交时间: 2021-03-17 22:30:58
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
stack = [root]
rs = []
while len(stack) != 0:
t = stack.pop()
if t:
rs.append(t.val)
if t.left:
stack.append(t.left)
if t.right:
stack.append(t.right)
rs.sort()
return rs[-k]