wordpress角色,淄博做网站优化,上海网站seoseodian,网站反链一般怎么做题目描述
给定一棵二叉搜索树#xff0c;请找出其中第 k 大的节点。 解题基本知识
二叉搜索树#xff08;Binary Search Tree#xff09;又名二叉查找树、二叉排序树。它是一棵空树#xff0c;或者是具有下列性质的二叉树#xff1a; 若它的左子树不空#xff0c;则左子…题目描述
给定一棵二叉搜索树请找出其中第 k 大的节点。 解题基本知识
二叉搜索树Binary Search Tree又名二叉查找树、二叉排序树。它是一棵空树或者是具有下列性质的二叉树 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空则右子树上所有结点的值均大于它的根结点的值 它的左、右子树也分别为二叉排序树。 解法一 递归 利用二叉搜索树的特性进行中序遍历。先遍历左节点然后根节点最后遍历右节点得到的是一个递增序列那么序列的倒序为递减序列。因此这道题我们可以转变为求二叉搜索树中序遍历倒序的第 k 个数。 /*** Definition for a binary tree node.* function TreeNode(val) {* this.val val;* this.left this.right null;* }*/
/*** param {TreeNode} root* param {number} k* return {number}*/
const kthLargest (root, k) {let res null; // 初始化返回值// 因为需要倒序第 k 个所以处理是右节点根节点然后左节点const dfs (root) {if (!root) return; // 如果当前节点为 null本轮处理结束dfs(root.right); // 开始处理右节点if (k 0) return; // k 值 为 0代表已经处理的节点超过目标节点本轮处理结束if (--k 0) {// 当 k 值 减 1 为 0表示已经到了我们想要的 k 大 节点保存当前值res root.val;}dfs(root.left); // 处理左节点};dfs(root); // 从初始化节点开始处理return res;
};复杂度分析 时间复杂度 O(N)无论 k 的值大小递归深度都为 N占用 O(N) 时间。空间复杂度 O(N)无论 k 的值大小递归深度都为 N占用 O(N) 空间。 解法二 迭代 思路还是二叉树的中序遍历利用栈的方式进行遍历。 /*** Definition for a binary tree node.* function TreeNode(val) {* this.val val;* this.left this.right null;* }*/
/*** param {TreeNode} root* param {number} k* return {number}*/
var kthLargest function (root, k) {if (!root) return 0;// 声明储存栈const stack [];// 判断当前栈否有节点和当前遍历节点位置while (stack.length || root) {while (root) {// 往栈里添加当前节点同时切换为右节点处理stack.push(root);root root.right;}// 取出当前栈顶元素根据添加的顺序当前元素是栈内最大的const cur stack.pop();k--;if (k 0) return cur.val;// 切换为左节点处理root cur.left;}return 0;
};复杂度分析 时间复杂度 O(N)需要遍历整棵树一次复杂度为 O(N)空间复杂度 O(N)需要额外空间栈进行储存树复杂度为 O(N)
