二叉搜索树的第k大节点——leetcode54

二叉搜索树的第k大节点

题目:二叉搜索树的第k大节点

给定一棵二叉搜索树,请找出其中第 k 大的节点的值。

示例:

输入: root = [3,1,4,null,2], k = 1    3   /   1   4       2 输出: 4

题解

方法1:分治法

class Solution {     int step, result;     public void dfs(TreeNode root)     {         if(root==null) return;         dfs(root.right);         if(--step==0) { result=root.val; return;}         dfs(root.left);     }     public int kthLargest(TreeNode root, int k) {         step=k;         dfs(root);         return result;     } }

方法2:非递归实现右根左遍历

class Solution0 {     public int kthLargest(TreeNode root, int k) {         Stack<TreeNode> stack=new Stack<>();         //压入所有右节点:遍历右根         while (root!=null)         {             stack.push(root);             root=root.right;         }          for(int i=0;i<k-1;i++)         {             TreeNode temp=stack.pop();             //压入左子树的所有右节点             if(temp.left!=null)             {                 temp=temp.left;                 while (temp!=null)                 {                     stack.add(temp);                     temp=temp.right;                 }             }         }          return stack.pop().val;     } }

推荐这些文章:

二叉搜索树的第k大节点——leetcode54

二叉搜索树的第k大节点
题目:二叉搜索树的第k大节点
给定一棵二叉搜索树,请找出其中第 k 大的节点的值。
示例:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4
题解:dfs
右根左遍历二叉树
class Solution {
private int result, count;
public void dfs(TreeNode root, int k){
if(root==null ...

450. 删除二叉搜索树中的节点

递归
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {

if (root == null){
return root;
}

/**
* 如果大于当前节点,就在左子树寻找;小于则在右子树寻找
* 相等则分三种情况:如果有一个孩子为空,则让另一个孩子作为新的根节点;否则,让左子树的最小节点成为新的根节点
*/
if (root.val > key){...

【每日一题】【树的dfs递归,返回多次,注意都遍历完后才最终返回】2022年1月6日-112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。
叶子节点 是指没有子节点的节点。
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/path-sum著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 

 
答案:

/**
* Definition for a binary tre...

leetcode 669. 修剪二叉搜索树

递归:
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root==null) return root;
if(root.val<low) return trimBST(root.right,low,high);
else if(root.val>high) return trimBST(root.left,low,high);
else{
root.left=trimBS...

腾讯五十题No.42 二叉搜索树的最近公共祖先

题目链接
//二叉搜索树的特性
class Solution {
TreeNode res = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
lca(root,p,q);
return res;
}
public void lca(TreeNode root,TreeNode p,TreeNode q){
//如果在根节点的两边,最小公共祖先就是根节点
if((root.val...

Leetcode701/450/669之二叉搜索树的插入删除修剪

二叉搜索树的插入删除修剪
Leetcode701-二叉搜索树中的插入操作

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
输入:root = [4,2,7,1,3], val = 5
输出:[4,2,7,1,3,5]

public TreeNode insertIntoBST(TreeNode root, int val) {
...

783. 二叉搜索树节点最小距离 二叉树中序遍历

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。
https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
...

腾讯五十题 No.42 二叉树的最近公共祖先

题目链接
注意p,q必然存在树内, 且所有节点的值唯一!!!
递归思想, 对以root为根的(子)树进行查找p和q, 如果root == null || p || q 直接返回root
表示对于当前树的查找已经完毕, 否则对左右子树进行查找, 根据左右子树的返回值判断:
1. 左右子树的返回值都不为null, 由于值唯一左右子树的返回值就是p和q, 此时root为LCA
2. 如果左右子树返回值只有一个不为null, 说明只有p和q存在与左或右子树中, 最先找到的那个节点为LCA
3. 左右子树返回值均为null, p和q均不在树中, 返回null
class Solution {
...

腾讯五十题No.40二叉树搜索中第k小的元素

题目链接
二叉树特点左子树小于根节点根节点小于右子树
class Solution {
public int kthSmallest(TreeNode root, int k) {
//左子树节点个数
int leftN = findChild(root.left);
//如果k等于左子树节点加一,则第k个数为根节点
if(leftN + 1 == k) return root.val;
//如果小于左子树节点个数,就递归左子树
else if(k <= leftN){
...

Leetcode235/236之树最近公共祖先以及递归中带TreeNode

树最近公共祖先以及递归中带TreeNode

但递归时返回TreeNode要想清楚最后一步返回到哪

Leetcode236-二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {...

文章标题:二叉搜索树的第k大节点——leetcode54
文章链接:https://www.dianjilingqu.com/2080.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>