带你快速刷完67道剑指offer
如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备 、简历 、实习 、校招总结 、offer选择 、也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载
# No62、二叉搜索树的第K个节点
# 题目描述
给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
# 示例1
输入
{5,3,7,2,4,6,8},3
1
返回值
{4}
1
说明 按结点数值大小顺序第三小结点的值为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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 二刷:
# 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18