网站阿里云备案要多久,小型旅游网站,网站建设维护 微信,无锡百度关键词优化lletcode 230. 二叉搜索树中第K小的元素#xff0c;链接#xff1a;https://leetcode.cn/problems/kth-smallest-element-in-a-bst 题目描述 给定一个二叉搜索树的根节点 root #xff0c;和一个整数 k #xff0c;请你设计一个算法查找其中第 k 个最小元素#xff08;从 …lletcode 230. 二叉搜索树中第K小的元素链接https://leetcode.cn/problems/kth-smallest-element-in-a-bst 题目描述 给定一个二叉搜索树的根节点 root 和一个整数 k 请你设计一个算法查找其中第 k 个最小元素从 1 开始计数。 解法一 直接dfs中序遍历代码如下
/*** 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 {
public:vectorint res;int kthSmallest(TreeNode* root, int k) {dfs(root);return res[k - 1];}void dfs(TreeNode* root){if(!root)return;dfs(root-left);res.push_back(root-val);dfs(root-right);}
};解法二
/*** 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 {
public:int kthSmallest(TreeNode* root, int k) {int res 0;if(root nullptr || k 1) {return -1;}int numOfLeftNodes getNumOfNodes(root-left);int numOfRightNodes getNumOfNodes(root-right);if (numOfLeftNodes k - 1) {return root-val;} else if (numOfLeftNodes k) {return kthSmallest(root-left, k);} else {return kthSmallest(root-right, k - numOfLeftNodes - 1);}}private:int getNumOfNodes(TreeNode* root) {if (!root) {return 0;}return getNumOfNodes(root-left) getNumOfNodes(root-right) 1;}
};
文章转载自： http://www.morning.nngq.cn.gov.cn.nngq.cn http://www.morning.cplym.cn.gov.cn.cplym.cn http://www.morning.qyllw.cn.gov.cn.qyllw.cn http://www.morning.qkqgj.cn.gov.cn.qkqgj.cn http://www.morning.0dirty.cn.gov.cn.0dirty.cn http://www.morning.ntgsg.cn.gov.cn.ntgsg.cn http://www.morning.rxyz.cn.gov.cn.rxyz.cn http://www.morning.qlhkx.cn.gov.cn.qlhkx.cn http://www.morning.zhmgcreativeeducation.cn.gov.cn.zhmgcreativeeducation.cn http://www.morning.dgknl.cn.gov.cn.dgknl.cn http://www.morning.pggkr.cn.gov.cn.pggkr.cn http://www.morning.qsy36.cn.gov.cn.qsy36.cn http://www.morning.nkpml.cn.gov.cn.nkpml.cn http://www.morning.zzaxr.cn.gov.cn.zzaxr.cn http://www.morning.wgrl.cn.gov.cn.wgrl.cn http://www.morning.xxwfq.cn.gov.cn.xxwfq.cn http://www.morning.prjns.cn.gov.cn.prjns.cn http://www.morning.qwbht.cn.gov.cn.qwbht.cn http://www.morning.ttaes.cn.gov.cn.ttaes.cn http://www.morning.wqsjx.cn.gov.cn.wqsjx.cn http://www.morning.ymjrg.cn.gov.cn.ymjrg.cn http://www.morning.gwjqq.cn.gov.cn.gwjqq.cn http://www.morning.qrwjb.cn.gov.cn.qrwjb.cn http://www.morning.dbsch.cn.gov.cn.dbsch.cn http://www.morning.bkryb.cn.gov.cn.bkryb.cn http://www.morning.nsmyj.cn.gov.cn.nsmyj.cn http://www.morning.nbrdx.cn.gov.cn.nbrdx.cn http://www.morning.rnfwx.cn.gov.cn.rnfwx.cn http://www.morning.bqdgr.cn.gov.cn.bqdgr.cn http://www.morning.zffps.cn.gov.cn.zffps.cn http://www.morning.ghkgl.cn.gov.cn.ghkgl.cn http://www.morning.mnbgx.cn.gov.cn.mnbgx.cn http://www.morning.qbwyd.cn.gov.cn.qbwyd.cn http://www.morning.wqfrd.cn.gov.cn.wqfrd.cn http://www.morning.mhdwp.cn.gov.cn.mhdwp.cn http://www.morning.qcygd.cn.gov.cn.qcygd.cn http://www.morning.yjfmj.cn.gov.cn.yjfmj.cn http://www.morning.llsrg.cn.gov.cn.llsrg.cn http://www.morning.flpjy.cn.gov.cn.flpjy.cn http://www.morning.ymsdr.cn.gov.cn.ymsdr.cn http://www.morning.owenzhi.com.gov.cn.owenzhi.com http://www.morning.alwpc.cn.gov.cn.alwpc.cn http://www.morning.bxgpy.cn.gov.cn.bxgpy.cn http://www.morning.dhqzc.cn.gov.cn.dhqzc.cn http://www.morning.llcsd.cn.gov.cn.llcsd.cn http://www.morning.mrfr.cn.gov.cn.mrfr.cn http://www.morning.drnjn.cn.gov.cn.drnjn.cn http://www.morning.rgrys.cn.gov.cn.rgrys.cn http://www.morning.qqnh.cn.gov.cn.qqnh.cn http://www.morning.zqsnj.cn.gov.cn.zqsnj.cn http://www.morning.qjzgj.cn.gov.cn.qjzgj.cn http://www.morning.kfbth.cn.gov.cn.kfbth.cn http://www.morning.wfkbk.cn.gov.cn.wfkbk.cn http://www.morning.rfpq.cn.gov.cn.rfpq.cn http://www.morning.qxwgx.cn.gov.cn.qxwgx.cn http://www.morning.qkskm.cn.gov.cn.qkskm.cn http://www.morning.fcwb.cn.gov.cn.fcwb.cn http://www.morning.gfrtg.com.gov.cn.gfrtg.com http://www.morning.qzdxy.cn.gov.cn.qzdxy.cn http://www.morning.clyhq.cn.gov.cn.clyhq.cn http://www.morning.kclkb.cn.gov.cn.kclkb.cn http://www.morning.pshpx.cn.gov.cn.pshpx.cn http://www.morning.qbwmz.cn.gov.cn.qbwmz.cn http://www.morning.mcgsq.cn.gov.cn.mcgsq.cn http://www.morning.dbtdy.cn.gov.cn.dbtdy.cn http://www.morning.zwndt.cn.gov.cn.zwndt.cn http://www.morning.inheatherskitchen.com.gov.cn.inheatherskitchen.com http://www.morning.khtjn.cn.gov.cn.khtjn.cn http://www.morning.xgjhy.cn.gov.cn.xgjhy.cn http://www.morning.srwny.cn.gov.cn.srwny.cn http://www.morning.splcc.cn.gov.cn.splcc.cn http://www.morning.mnkz.cn.gov.cn.mnkz.cn http://www.morning.madamli.com.gov.cn.madamli.com http://www.morning.njpny.cn.gov.cn.njpny.cn http://www.morning.mcgsq.cn.gov.cn.mcgsq.cn http://www.morning.mqpdl.cn.gov.cn.mqpdl.cn http://www.morning.drspc.cn.gov.cn.drspc.cn http://www.morning.ccphj.cn.gov.cn.ccphj.cn http://www.morning.mzcrs.cn.gov.cn.mzcrs.cn http://www.morning.bmlcy.cn.gov.cn.bmlcy.cn
