优于网上博客:从LeetCode 230. Kth Smallest Element in a BST学习去冗余,分治,二叉树遍历等


题意是,给你一个BST,让找到第K大数。

这道题,我一看,BST的一个非常重要的性质就是中序遍历的结果是一个有序序列,那我把中序遍历的结果放到一个数组里,输出第k个数就可以了。

解法一:简单易懂,没毛病, AC完我看了一下,并不需要向博客上那样判断k-1的根节点情况,so easy。
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if (root == NULL){
            return 0;
        }
        cnt = k;
        dfs(root);
        return t[k - 1];
    }
    
    void dfs(TreeNode *root){
        if (root == NULL){
            return;
        }
        dfs(root->left);
        cnt--;
        t.push_back(root->val);
        if (cnt == 0){
            return;
        }
        dfs(root->right);
    }
private:
    int cnt , ans = 0;
    vector<int> t;
};


林奔大神多次强调去冗余,我一看我用了一个vector,记录的数除了最后一个也没用过,那么我其实只需要记录最后一个数就可以了。
解法二:
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if (root == NULL){
            return 0;
        }
        cnt = k;
        dfs(root);
        return ans;
    }
    
    void dfs(TreeNode *root){
        if (root == NULL){
            return;
        }
        dfs(root->left);
        cnt--;
        if (cnt == 0){
            ans = root->val;
            return;
        }
        dfs(root->right);
    }

private:
    int cnt , ans = 0;
};


这样我就把O(n)的vector空间省下来了,AC没毛病。再一想,递归的执行速度是没有循环快的,我可以写成循环的版本追求更好的效果,顺便练习一下递归遍历转循环遍历代码:
解法三:
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if (root == NULL){
            return 0;
        }
        cnt = k;
        inOrder(root);  
        return ans;
    }
    
    void inOrder(TreeNode * root){
        stack<TreeNode *>st;
        while (!st.empty() || root != NULL){ 
            while(root != NULL){
                st.push(root);
                root = root->left;
            }
            if (!st.empty()){
                root = st.top();
                cnt--;
                st.pop();
                if (cnt == 0){
                    ans = root->val;
                    return;
                }
                root = root->right;
            }
        }
    }

private:
    int cnt , ans = 0;
};


上面的解法是我自己做出来的,看网上博客还有许老师说的一种分治法,其实时间复杂度一点也不必上面的有优势,空间复杂度也都是一样的,也比前面的解法难理解一些。但是,树这种天生适合分治递归的数据结构,碰到问题还是可以往分治想的。

解法四:
class Solution {
public:
    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* node) {
        if (!node) return 0;
        return 1 + count(node->left) + count(node->right);
    }
};


还有一种,就是许老师上课说的,也是比网上大多数代码要好的,就是在计算左子树节点数目的过程中,有必要才计算右子树,是比上面的分治节省时间的:
解法五:
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if (root == NULL || k <= 0){
            return 0;
        }
        
        dfs(root, k);
        
        return ans->val;
    }
    
    int dfs(TreeNode *root, int k){
        if (root == NULL){
            return 0;
        }
        
        int countLeft = dfs(root->left, k);
        int countRight = 0;
        if (k <= countLeft || ans != NULL){
            return 0;
        }else{
            if (k - countLeft == 1){
                ans = root;
                return 0;
            }else{
                countRight = dfs(root->right, k - countLeft - 1);
            }
        }
        return 1 + countLeft + countRight;
    }
    
private:
    TreeNode *ans = NULL;
};


看这个代码总觉得有点冗余,于是就优化了一下,代码和判断条件更少,也更容易理解:
解法六:
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if (root == NULL || k <= 0){
            return 0;
        }
        
        dfs(root, k);
        
        return ans->val;
    }
    
    int dfs(TreeNode *root, int k){
        if (root == NULL || ans != NULL){
            return 0;
        }
        
        int countLeft = dfs(root->left, k);
        int countRight = 0;

        if (k - countLeft == 1){
            ans = root;
        }else if(k > countLeft + 1){
            countRight = dfs(root->right, k - countLeft - 1);
        }

        return 1 + countLeft + countRight;
    }
    
private:
    TreeNode *ans = NULL;
};

1 个评论

可以发成问题哦,不发文章

要回复文章请先登录注册

返回顶部