62、二叉搜索树的第K个节点 过
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
示例1
输入
{5,3,7,2,4,6,8},3
返回值
{4}
说明
按结点数值大小顺序第三小结点的值为4
1、笨方法，全部保存下来
会超时，这个方法不行
2、中序遍历其实就是从小到大的排列顺序
class situation {
public:
int count=0;
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if (pRoot == nullptr) return nullptr;
TreeNode* left_node = KthNode(pRoot->left, k);
if (left_node) return left_node;
count++;
if (k == count) {
return pRoot;
}
TreeNode* right_node = KthNode(pRoot->right, k);
if (right_node) return right_node;
return nullptr;
}
}
3、中序遍历模板解法
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if (pRoot == nullptr) return nullptr;
stack<TreeNode*> s;
s.push(pRoot);
while (!s.empty() || pRoot != nullptr) {
if (pRoot != nullptr) {
s.push(pRoot);
pRoot = pRoot->left;
}
else {
pRoot = s.top();
s.pop();
k--;
if (k == 0) return pRoot;
pRoot = pRoot->right;
}
}
return nullptr;
}
二刷：
1、其实就是中序遍历
运行时间：3ms 占用内存：504k
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if(pRoot == nullptr) return nullptr;
stack<TreeNode*> st;
while(!st.empty() || pRoot!=nullptr){
while(pRoot != nullptr){
st.push(pRoot);
pRoot = pRoot->left;
}
pRoot = st.top();
st.pop();
if(--k == 0) return pRoot;
pRoot = pRoot->right;
}
return nullptr;
}
美女帅哥们如果觉得写的还行，有点用的话麻烦点个赞或者留个言支持一下阿秀~
如果觉得狗屁不通，直接留言开喷就完事了。