刷题之二叉搜索树中第k小的元素(leetcode)

二叉搜索树中第k小的元素

注意二叉搜索树的性质：在二叉搜索树中，任意子节点都满足“左子节点 < 根节点 <<右子节点”的规则。因此二叉搜索树具有一个重要性质：二叉搜索树的中序遍历为递增序列。

当成数组来算，复杂度比较高：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int kthSmallest(TreeNode* root, int k) {vector<int>nums;travel(root,nums);return nums[k-1];}void travel(TreeNode* root,vector<int>&vec){if(root==NULL)return;travel(root->left,vec);vec.push_back(root->val);travel(root->right,vec);}};

比较好的解法，只计数前k个：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:int k;int res=0;void travel(TreeNode* root){if(root==NULL)return;travel(root->left);if(k==0)//只需要数前k个就行了return;k--;if(k==0)//记录第k个res=root->val;travel(root->right);}
public:int kthSmallest(TreeNode* root,int k) {this->k=k;travel(root);return res;}
};