小型企业网络营销方案,西安seo优化系统,杭州市下城区建设厅网站,做企业网站要注意什么题目#xff1a;
给定一棵二叉搜索树#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 限制#xff1a;
1 ≤ 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 限制
1 ≤ k ≤ 二叉搜索树元素个数
-------------------------------------------------------------------------------------------------------------------------------
分析 二叉搜索树的特点就是根左根根右所以我们经过思考可知通过中序遍历左中右得到的是二叉搜索树值的升序。 因为我们要得到第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 count,res;public int kthLargest(TreeNode root, int k) {this.count k;method(root);return res;}public void method(TreeNode root) {if(rootnull) return;if(count 0) return;method(root.right);count--;if(count0) {res root.val;}method(root.left);}
}
因为进入递归之后记录数据k很乱所以我们定义两个类变量count用来记录当前是第几个结点和res用来存储第K大的值。
思考
之前我总是想不通为什么method(root.right);调用后要count-- 表示这个结点已经被遍历。
那method(root.left); 后面为什么不count-- 呢
后来我想通了我能提出这个问题说明我没懂递归的真谛。这个count--不是method(root.right);的count--。而是root的count-- 说明root这个结点被遍历到了。
递归整体可以这么理解你就想先遍历一个结点不带递归 public void method(TreeNode root) {if(rootnull) return;if(count 0) return;count--;if(count0) {res root.val;}}
当我把递归删掉后我的目的就是遍历一个结点。
但是当我有遍历需求后我想先看右边的再遍历左边的。那么我就直接上下加个递归。
即 public void method(TreeNode root) {if(rootnull) return;if(count 0) return;method(root.right);count--;if(count0) {res root.val;}method(root.left);}
你可以将复杂的逻辑改成打印一个结点那么我想先打印左再中再右。那么就上下加递归函数就可以了。
void method(TreeNode root) {if(root null) return;method(root.left); //左System.out.println(root.val); //打印method(root.right); //右
}就是这样。
