剑指—二叉搜索树的第k大节点
剑指 Offer 54. 二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1: 输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 4 示例 2: 输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 输出: 4 复制代码
来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/er…
第一种方法
一直将右子树的节点不断压栈
右子树为空的时候，弹栈作为当前节点去遍历其左子树
计数器加1，当计数器等于k的时候直接返回
class Solution { public int kthLargest(TreeNode root, int k) { Stack<TreeNode> stack = new Stack<>(); int count = 1; //根节点本身算1 while(Objects.nonNull(root) || !stack.empty()){ while(Objects.nonNull(root)){ stack.push(root); //不为空 则入栈 root = root.right; //右子树比根大，所以下一步直接到右子树 } TreeNode pop = stack.pop(); if(count == k){ return pop.val; //已经找到为第k个大的节点 } count++; root = pop.left; //右节点的遍历以后，来到子根节点的左子树 } return 0; } } 复制代码第二种方法更为直观一点
利用二叉搜索树的特性
二叉搜索树的中序遍历就是从大到小输出
那么每次遍历一个元素，
k做自减操作
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); } }
作者：xiaoff
链接：https://juejin.cn/post/7016865212032614408