响应式网站的登录设置,制作企业网站页面代码摄影 开课吧,html网页源代码查看,本地常州微信网站建设【问题描述】[简单]
给定一棵二叉搜索树#xff0c;请找出其中第k大的节点。示例 1:
输入: root [3,1,4,null,2], k 13/ \1 4\2
输出: 4
示例 2:输入: root [5,3,6,2,4,null,null,1], k 35/ \3 6/ \2 4/1
输出: 4【解答思路】
反向中序遍历 遍历到第k个节点时请找出其中第k大的节点。示例 1:
输入: root [3,1,4,null,2], k 13/ \1 4\2
输出: 4
示例 2:输入: root [5,3,6,2,4,null,null,1], k 35/ \3 6/ \2 4/1
输出: 4
【解答思路】
反向中序遍历 遍历到第k个节点时直接返回改节点值如果未找到则返回0
1. 递归 时间复杂度O(N) 空间复杂度O(1)
class Solution {int res, k;public int kthLargest(TreeNode root, int k) {this.k k;dfs(root);return res;}void dfs(TreeNode root) {if(root null) return;dfs(root.right);if(k 0) return;if(--k 0) res root.val;dfs(root.left);}
}
nt count0, res0;//形参k不能随着dfs的迭代而不断变化为了记录迭代进程和结果引入类变量count和res。public int kthLargest(TreeNode root, int k) {this.countk;//利用形参值k对类变量count进行初始化dfs(root);//这里不要引入形参kdfs中直接使用的是初始值为k的类变量countreturn res; }public void dfs(TreeNode root){if(rootnull||count0) return;//当root为空或者已经找到了res时直接返回dfs(root.right);if(--count0){//先--再判断res root.val;return;//这里的return可以避免之后的无效迭代dfs(root.left);}dfs(root.left); }2. 迭代
如下图5372468 中按节点数值大小顺序第三小结点的值为4 时间复杂度O(N) 空间复杂度O(1)
class Solution {// 反向中序遍历当遍历到第k个节点时返回该节点值public int kthLargest(TreeNode root, int k) {// count用于指示已经查找过的数字个数int count0;TreeNode p root;StackTreeNode stacknew Stack();while(p!null||!stack.isEmpty()){if(p!null){stack.push(p);pp.right;}else{pstack.pop();count;if(countk) return p.val;pp.left;}}return 0;}
}
2. 入队
时间复杂度O(N) 空间复杂度O(N)
class Solution {public int kthLargest(TreeNode root, int k) {// 在中序遍历的同时把值加入表中ArrayListInteger list new ArrayList();r(root,list);//话说倒数第k个数下标是多少来着诶倒数第一个数下标是size-1诶那么倒数第k个数不就是return list.get(list.size() - k);}// 二叉树递归形式中序遍历void r(TreeNode root, List list){if(root null) return ;r(root.left,list);list.add(root.val);r(root.right,list);}
}
class Solution {public int kthLargest(TreeNode root, int k) {ListInteger result new LinkedList();StackTreeNode stack new Stack();TreeNode cur root;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {stack.push(cur);cur cur.right;}cur stack.pop();result.add(cur.val);cur cur.left;}return result.get(k - 1);}
}
【总结】
1. 二叉搜索树中序遍历 有序递增序列 中序逆序遍历 有序递减序列
2.二叉树遍历
前序遍历 先输出当前结点的数据再依次遍历输出左结点和右结点中序遍历 先遍历输出左结点再输出当前结点的数据再遍历输出右结点后续遍历 先遍历输出左结点再遍历输出右结点最后输出当前结点的数据
3. 二叉树 递归 栈
转载链接https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/solution/mian-shi-ti-54-er-cha-sou-suo-shu-de-di-k-da-jie-d/
参考链接https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/solution/sou-suo-er-cha-shu-de-zhong-xu-bian-li-jiu-shi-di-/
参考链接https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/solution/fan-xiang-zhong-xu-bian-li-fei-di-gui-die-dai-miao/
