AcWing 70 二叉搜索树的第k个结点
程序员文章站
2022-05-20 13:49:49
...
题目描述:
给定一棵二叉搜索树,请找出其中的第k小的结点。
你可以假设树和k都存在,并且1≤k≤树的总结点数。
样例
输入:root = [2, 1, 3, null, null, null, null] ,k = 3
2
/ \
1 3
输出:3
分析:
模拟二叉树中序遍历过程,依次访问LNR,访问N的语句替换为k--即可。当k到达0时,找到答案,递归不再深入。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* ans;
TreeNode* kthNode(TreeNode* root, int k) {
inorder(root,k);
return ans;
}
void inorder(TreeNode* root,int& k){
if(k <= 0 || !root) return;
inorder(root->left,k);
k--;
if(!k) ans = root;
inorder(root->right,k);
}
};