首页 > 其他分享 >230. 二叉搜索树中第K小的元素

230. 二叉搜索树中第K小的元素

时间:2024-03-10 10:55:05浏览次数:31  
标签:right TreeNode int 树中 二叉 return root 230 left

230. 二叉搜索树中第K小的元素

 https://leetcode.cn/problems/kth-smallest-element-in-a-bst/  

思路

https://leetcode.cn/problems/kth-smallest-element-in-a-bst/solutions/1050055/er-cha-sou-suo-shu-zhong-di-kxiao-de-yua-8o07/ 根据二叉搜索树性质, 对左子树进行搜索目标, 根节点判断, 然后对右子树进行目标搜索。

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    int count = 0;
public:
    int kthSmallest(TreeNode* root, int k) {
        return inorder(root, k);
    }
private:
    /*
    return kth value if found in this root, otherwise -1
    */
    int inorder(TreeNode* root, int k){
        if (root->left){
            int leftret = inorder(root->left, k);
            if (leftret != -1){
                return leftret;
            }
        }

        count++;
        if (count == k){
            return root->val;
        }

        if (root->right){
            int rightret = inorder(root->right, k);
            if (rightret != -1){
                return rightret;
            }
        }

        return -1;
    }
};

 

 

标签:right,TreeNode,int,树中,二叉,return,root,230,left
From: https://www.cnblogs.com/lightsong/p/18063844

相关文章

  • 代码随想录 第十六天 | ● 104.二叉树的最大深度 559.n叉树的最大深度 ● 111.二叉树
    leetcode:104.二叉树的最大深度-力扣(LeetCode)思路:递归判断每次左右节点的是否存在,存在自然加一,return的1就是这样,判断子节点的左右两端是否有节点,统计有的节点数量,也就是左右的高度classSolution{publicintmaxDepth(TreeNoderoot){//后序遍历if......
  • abc230E n/i分数求和
    题面:给定n,计算$\sum_{i=1}^{n}\frac{n}{i}$范围:1<=n<=1E12思路:分块,假设区间[l,r]的结果都相同,即n/l=n/r,根据l可以推算出r,那么这个区间对结果的贡献就是区间长度乘以结果,时间复杂度为O(sqrtn)。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#define......
  • 代码随想录算法训练营day17 | leetcode 110. 平衡二叉树、257. 二叉树的所有路径、404
    目录题目链接:110.平衡二叉树-简单题目链接:257.二叉树的所有路径-简单题目链接:404.左叶子之和-简单题目链接:110.平衡二叉树-简单题目描述:给定一个二叉树,判断它是否是平衡二叉树示例1:输入:root=[3,9,20,null,null,15,7]输出:true示例2:输入:root=[1,2,2,3,3,null,nul......
  • 代码随想录 第十五天 | ● 层序遍历 10 ● 226.翻转二叉树 ● 101.对称二叉树 2 感
    leetcode:102.二叉树的层序遍历-力扣(LeetCode)思路:用队列长度控制弹栈的多少,不等于空时获取root,因为传了一个根肯定是1,接下来找左右节点,将根节点弹出,获取下一次的size,一直到空。。。//102.二叉树的层序遍历classSolution{publicList<List<Integer>>resList=newA......
  • 代码随想录算法训练营第四十天|● 343. 整数拆分 ● 96.不同的二叉搜索树
    整数拆分 题目链接:343.整数拆分-力扣(LeetCode)思路:第一步想的是用递归做,intdigui(intn){if(n==1)returnn;returnmax((n/2)*(n-n/2),digui(n/2)*digui(n-n/2));}可惜的是题目并没有规定一定要分成两份,因此这个思路是不对的,但已经初窥门径。......
  • 代码随想录算法训练营第四十天 | 96.不同的二叉搜索树,343. 整数拆分
    343.整数拆分 已解答中等 相关标签相关企业 提示 给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k>=2 ),并使这些整数的乘积最大化。返回 你可以获得的最大乘积 。 示例1:输入:n=2输出:1解释:2=1+1,1×1=1。......
  • 538. 把二叉搜索树转换为累加树c
    右根左遍历就行。/***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/voidorder(structTreeNode*root,int*pre){if(!root)return;order(root->right,pr......
  • 108. 将有序数组转换为二叉搜索树c
    如果按一般思路建一个平衡二叉树,非常麻烦。但是二分查找树就一个平衡二叉树,所有构建二叉查找树就行。/***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/structTree......
  • 669. 修剪二叉搜索树c
    这题还是很难得。一看是想着当作普通二叉树所有节点都递归,但是很难做,难度很高。/***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/structTreeNode*preorde(structT......
  • 450. 删除二叉搜索树中的节点c
    这题特别好,和递归删除链表里的元素有异曲同工之妙/***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/structTreeNode*leftleave(structTreeNode*root){root=r......