剑指offer54 二叉搜索树的第k大节点【DFS】
题目描述
给定一棵二叉搜索树,请找出其中第k大的节点。
示例 1:
1 | 输入: root = [3,1,4,null,2], k = 1 |
示例 2:
1 | 输入: root = [5,3,6,2,4,null,null,1], k = 3 |
限制:
1 ≤ k ≤ 二叉搜索树元素个数
解题思路
方法一:深度优先搜索DFS
类似中序遍历思想,先遍历右子树后遍历左子树的,访问根节点时,对k进行减一操作,当k==0时,退出递归,设置res.
实现代码
1 | class Solution54 { |
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n) // 递归栈空间
资料
剑指offer54 二叉搜索树的第k大节点【DFS】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.