题解 | #二叉搜索树的第k个结点#
二叉搜索树的第k个结点
http://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a
题目描述：给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。
示例1
输入：{5,3,7,2,4,6,8},3
返回值：4
说明：按结点数值大小顺序第三小结点的值为4
思路：二叉搜索树是一棵已经排序好的树，对BST（Binary Search Tree）的中序遍历即可得到从小到大的所有值，因此采用中序遍历方法获得第k个节点即可返回。具体代码如下：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
int i=0;
TreeNode *p;
void midorder(TreeNode *root,int k)
{
if(root != NULL)
{
midorder(root->left,k);
i++;
if(i == k)
p = root;
midorder(root->right,k);
}
}
TreeNode* KthNode(TreeNode* pRoot, int k) {
midorder(pRoot,k);
return p;
}
};
Klook客路公司氛围 19人发布
投递快手等公司8个岗位
