L230 二叉搜索树中第K小的元素

树 查找

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

解：二叉搜索树中序遍历得到从小到大的排序数组。

 //分治解法，统计左子树节点个数，用K判断在哪个子树里
    int kthSmallest(TreeNode* root, int k){
        int cnt = count(root->left);
        if(k<=cnt){
            return kthSmallest(root->left, k);
            }
        else if(k>cnt+1){
            return kthSmallest(root->right, k-cnt-1);
        }
        return root->val;
    }
    int count(TreeNode* root){
        if(!root) return 0;
        return 1+count(root->left)+count(root->right);
    }

////非递归解法，注意条件为CNT==K,STACK,P
int kthSmallest(TreeNode* root, int k){
    int cnt=0;
    stack<TreeNode*> s;
    TreeNode *p=root;
    // 左 中 右
    while(p || !s.empty()){
        while(p){
            s.push(p);
            p = p->left;
        }
        p = s.top(); s.pop();
        ++cnt;
        if(cnt == k) return p->val;
        p = p->right;
    }
    return 0;
}

////递归解法

    vector<int> num;
    int kthSmallest(TreeNode* root, int k) {
        posOrd(root);
        return num[k-1];
    }
    void posOrd(TreeNode* root){
        if(root == NULL) return;
        posOrd(root->left);
        num.push_back(root->val);
        posOrd(root->right);
    }

原本解法

class Solution {
public:
    vector<int> num;
    int kthSmallest(TreeNode* root, int k) {
        posOrd(root);
        return num[k-1];
    }
    void posOrd(TreeNode* root){
        if(root == NULL) return;
        posOrd(root->left);
        num.push_back(root->val);
        posOrd(root->right);
    }
};