网站设计建设，网络营销推广,山东华建建设有限公司网站,wordpress 付费后查看,易营宝智能建站平台剑指 Offer 54. 二叉搜索树的第k大节点 给定一棵二叉搜索树#xff0c;请找出其中第 k 大的节点的值。 我的思路是#xff1a;用一个全局arrayList不断收集“逆向”中序遍历该搜索二叉树所需要的答案
class Solution {int res, k;public int kthLargest(TreeNode root, int …剑指 Offer 54. 二叉搜索树的第k大节点 给定一棵二叉搜索树请找出其中第 k 大的节点的值。 我的思路是用一个全局arrayList不断收集“逆向”中序遍历该搜索二叉树所需要的答案
class Solution {int res, k;public int kthLargest(TreeNode root, int k) {this.k k; // !! 注意这里this的使用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);}
}作者jyd
链接https://leetcode.cn/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/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {ArrayListInteger list new ArrayList();public int kthLargest(TreeNode root, int k) {preOrder(root);return list.get(k-1);}public void preOrder(TreeNode root){if(root!null){preOrder(root.right); list.add(root.val);preOrder(root.left);}}
}下面是大佬K神的思路 使用全局变量一遍遍历一遍数数到第k个最大的数时就返回。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {int res0,kk0;public int kthLargest(TreeNode root, int k) {kkk;inverseInOrder(root);return res;}public void inverseInOrder(TreeNode root){if(root!null){inverseInOrder(root.right);if(kk0) return;if(kk-10) resroot.val;kk--;inverseInOrder(root.left);}}
}
