网站建设自己怎么做,软件工程要学什么,app开发公司未按照合同开发,门户网站制作全包题目链接#xff1a;https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
1. 题目介绍#xff08; 54. 二叉搜索树的第k大节点#xff09; 给定一棵二叉搜索树#xff0c;请找出其中第 k 大的节点的值。 【测试用例】#xff1a; 示例 1: 示例2https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
1. 题目介绍 54. 二叉搜索树的第k大节点 给定一棵二叉搜索树请找出其中第 k 大的节点的值。 【测试用例】 示例 1: 示例2
【条件约束】 限制 1 ≤ k ≤ 二叉搜索树元素个数 2. 题解
2.1 中序遍历 – O(n)
时间复杂度O(n)空间复杂度O(1) 【解题思路】 由于题目给的树是 二叉搜索树 即 具有以下性质 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树。 …… 因此若对它进行中序遍历则是一颗递增的排好序的序列 如上图所示这是一棵有7个节点的二叉搜索树它的中序遍历序列为 {2345678} …… 该题要求我们求的是 一棵二叉搜索树的 第 k 大节点那么就应该对应着中序遍历序列的 倒数第 k 个节点以上面的二叉搜索树为例第 1 大节点应为 8第 2 大节点应为 7依次类推原书中的举例应该是错的它说按节点数值大小顺序第3大节点的值是4感觉这里应该是说错了 …… 【实现策略】 思路理清了我们就可以愉快的写代码了 中序倒序遍历右、根、左求 第 k 大同理中序正序遍历左、根、右可以用来求 第 k 小 判断无效输入头节点是否为空k是否小于等于0以递归的形式 dfs() 来进行中序倒叙遍历按照右、根、左 的顺序定义一个全局的 计数变量 idx用来确认当前节点是否已经到了第 k 大节点如果是则将值保存在 res 中(这里进一步简化的话可以省略掉 idx 变量转而直接操作 k 让 k--当 k 减至 0 时代表已找到目标节点无需再继续遍历)递归结束返回 res . /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {// Solution1中序遍历int res,idx 0;public int kthLargest(TreeNode root, int k) {// 无效输入判断if (root null || k 0) return -1;// 递归中序遍历dfs(root,k);// 最后返回结果return res;}void dfs(TreeNode root, int k) {// 递归终止条件if(root null) return;// 中序倒序遍历找最大dfs(root.right,k);idx;// 如果当前是第k大赋值给resif(idx k) res root.val;// 找左子树dfs(root.left,k);}
}3. 参考资料
[1] 面试题54. 二叉搜索树的第 k 大节点中序遍历 提前返回清晰图解
