LeetCode 剑指 Offer 54. 二叉搜索树的第k大节点

题目描述

✅ 剑指 Offer 54. 二叉搜索树的第k大节点

image-20241107211921075

image-20250418232003330

image-20250418232033538

思路分析

二叉搜索树有个重要性质：中序遍历为升序序列

image-20250510205014114

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25



// kthLargest
func findTargetNode(root *TreeNode, k int) int {
	count := 0
	res := 0

	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}

		inorder(node.Right)

		count++
		if count == k {
			res = node.Val
			return
		}

		inorder(node.Left)
	}

	inorder(root)
	return res
}





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20



// kthLargest
func findTargetNode(root *TreeNode, k int) int {
	var stack []*TreeNode
	cur := root

	for cur != nil || len(stack) > 0 {
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Right
		}
		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		k--
		if k == 0 {
			return cur.Val
		}
		cur = cur.Left
	}
	return -1
}
  • 时间复杂度：O(k)，每次只处理一个节点，总共访问 k 个。
  • 空间复杂度：O(k)，最多栈中存储 k 个节点。

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2024/73632605
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！