Given a binary search tree and an integer K, find K-th smallest element in BST.
For example:
Input:
2
/ \
1 3
K = 2
Output:
2
Note: Your solution musb be in-place without altering the nodes' values.
Solution 1:
in-order递归访问。
TreeNode* kth_smallest(TreeNode* root, int& k) { if(!root || k < 0 ) return nullptr; TreeNode* left = kth_smallest(root->left, k); if(left) return left; if(--k == 0) return root; return kth_smallest(root->right, k); }
Solution 2:
in-order非递归访问。
TreeNode* kth_smallest(TreeNode* root, int& k) { if(!root || k <= 0 ) return nullptr; TreeNode* node = root; stack<TreeNode *> st; while(!st.empty() || node) { if(node) { st.push(node); node = node->left; } else { TreeNode *p = st.top(); st.pop(); if(--k == 0) return p; if(p->right) node=p->right; } } return nullptr; }
相关推荐
378.Kth_Smallest_Element_in_a_Sorted_Matrix有序矩阵中第K小的元素【LeetCode单
703.Kth_Largest_Element_in_a_Stream数据流中的第K大元素【LeetCode单题讲解系列】
本人在Clion中的实现的第小k元素,有期望值是O(n)代价的以及醉话情况为O(n)BFPRT算法
lru cache leetcode Coding-Interview A repo for popular coding interview ...In ...In ...In ...二叉树查找/BST查找 Closest Binary Search Tree Value 二叉树查找/二叉树第K个 Kth Smallest Element In A
MatLab 中用于 GPS 跟踪的扩展卡尔曼滤波器实现。
this function returns kth smallest element in arr[l...r],using quicksort based method. without sorting all the elements in the list
纹理图像分类数据集,KTH-TIPS数据集,包含orange-peel、bread等10类纹理图像
8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two Sum II Input array is sorted 49 ...
KTH-TIPS 纹理材质数据.zip
从终点开始
KTH-ID1219:软件演进和维护 我学到了什么? 学习维护的维护类型和维护模型IEEE1219,ISO99,ITIL(纠正,自适应,完善,预防等)的过程模型 学习了软件生命周期的定义(开发,发展和淘汰),修订(重新设计) ...
matlab 通信论文仿真代码什么是GISOO? 对无线网络物理系统 (CPS) 日益增长的需求需要正确设计、实施和验证计算、通信和控制方法。 传统的仿真工具侧重于计算、通信或控制,当这三个方面相互作用时是不够的。...
傅里叶变换动图matlab代码
Smallest Element in a BST Review:高效的一些建议 Tip:Elastic Search VS Solr Share:人的一生两个最大的财富是:你的才华和你的时间 Algorithm:LC 763. Partition Labels Review:Signs that You are a Bad ...
用三种方法实现,随机生成的一堆数中选出Kth个数,包括简单选择排序、冒泡排序、快速排序
KTH,工程科学学院 Nikolaos Koukis 2015 年 1 月 该存储库包含为飞行力学课程编写的代码。 它包括来自 3 个主要项目工作的代码: 项目工作一 J35 Draken飞机的计算性能特点 超推力图 SEP图 优化超音速飞行的轨迹 ...
KTH-TIPS纹理灰度数据集,可以直接用于matlab图像分类
作业-KTH深度学习老实说,请不要窃。
lru缓存leetcode 力码 大批 152-最大乘积子阵列,169-多数元素,189-...215-Kth Largest element in an Array(Heap Sort), HARD: 218-The Skyline Problem(Mergesort) ) 动态规划 HARD: 174-Dungeon Game, HARD: 188
音乐转歌词该项目的灵感来自[1]。 执行说明: 从下载MIR-1K数据集执行create_dataset.py以拆分和预处理数据执行train.py训练网络执行eval.py评估网络[1] Huang,M。Kim,M。Hasegawa-Johnson和P....