美文网首页
2020-02-26 刷题 4 (二叉树,排序和搜索)

2020-02-26 刷题 4 (二叉树,排序和搜索)

作者: nowherespyfly | 来源:发表于2020-02-26 15:58 被阅读0次

    102 二叉树的层次遍历

    因为题目要求遍历的结果是一个二维列表,每一层节点的遍历结果是一个列表,所以每次出了入队树节点,还有该节点的深度。

    time: 4ms, memory: 15MB
    /**
     * 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:
        struct DNode{
            int depth;
            TreeNode *t;
            DNode(int d, TreeNode *n): depth(d), t(n){}
        };
    
        vector<vector<int>> levelOrder(TreeNode* root) {
            queue<DNode> q;
            vector<vector<int>> v;
            if(!root) return v;
            // initialize
            q.push(DNode(0, root));
            TreeNode *cur;
            int cur_dep = 0;
            vector<int> tmp_v;
            while(!q.empty()){
                cur = q.front().t;
                if(q.front().depth > cur_dep){
                    cur_dep =  q.front().depth;
                    v.push_back(tmp_v);
                    tmp_v.clear();
                }
                q.pop();
                tmp_v.push_back(cur -> val);
                if(cur -> left) q.push(DNode(cur_dep+1, cur -> left));
                if(cur -> right) q.push(DNode(cur_dep+1, cur -> right));
            }
            v.push_back(tmp_v);
            return v;
        }
    };
    

    108 将有序数组转换为二叉搜索树

    昨天做过一个二叉搜索树的题,给定的有序数组其实就是二叉树的中序遍历结果。恢复的结果有很多种,但由于限定了左右子树的高度差不能超过1,所以范围就小了很多。其实,还是有两种不同的做法,我选择的是左边高右边低;还可以左边低右边高,应该也不算错。
    解这种二分问题最怕的就是边界,第一关键就是统一区间,要么两边都左闭右开,要么两边都左闭右闭;第二就是边界条件,如果左闭右开,边界条件就是右下标小于等于左下标;否则,边界条件就是右下标小于左下标。
    最近不统计运行时间和内存了,每次跑都不一样,不太科学。
    代码:

    /**
     * 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* helperBST(vector<int>& nums, int left, int right){
            // [, )
            if(right <= left) return NULL;
            int mid = (right - left) /  2 + left;
            TreeNode *root = new TreeNode(nums[mid]);
            root -> left = helperBST(nums, left, mid);
            root -> right = helperBST(nums, mid+1, right);
            return root;
        }
        TreeNode* sortedArrayToBST(vector<int>& nums) {
            if(nums.size() == 0) return NULL;
            TreeNode *root = helperBST(nums, 0, nums.size());
            return root;
        }
    };
    

    88 合并两个有序数组

    最直接的想法就是用归并排序的想法,引入额外的数组来存放两个数组合并后的结果,最后拷贝回数组1:

    class Solution {
    public:
        void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
            int i=0, j = 0, k = 0;
            vector<int> nums;
            if(n==0) return;
            while(i < m && j < n){
                if(nums1[i] <= nums2[j]) nums.push_back(nums1[i++]);
                else nums.push_back(nums2[j++]);
            }
            while(i < m) nums.push_back(nums1[i++]);
            while(j < n) nums.push_back(nums2[j++]);
            nums1.clear();
            for(i = 0; i < m+n; i++)
                nums1.push_back(nums[i]);
        }
    };
    

    后来注意到,题干说,假设数组1有足够的空间,理解一下就是,m不是nums1的size。那就很简单了,从后向前扫描两个数组,将当前比较的更大的值拷贝到指定的位置。因为是从后向前扫描,所以不用担心覆盖问题。

    class Solution {
    public:
        void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
            int i = m - 1, j = n - 1, k = m + n - 1;
            while(k >= 0 && i >= 0 && j >= 0){
                if(nums1[i] >= nums2[j]){
                    nums1[k--] = nums1[i--];
                }
                else nums1[k--] = nums2[j--];
            }
            while(k >= 0){
                if(i >= 0) nums1[k--] = nums1[i--];
                else nums1[k--] = nums2[j--];
            }
        }
    };
    

    278 第一个错误的版本

    标签:二分查找
    比较简单的二分查找题目,还是需要注意区间和边界。
    1)经过几题我发现,比较好的卡区间的方法就是,确保正确答案一定在选择的区间里,已经验证过的错误的答案一定不在选择的区间里。
    2)至于防止死循环的方法,就是确保每次区间一定是缩小的。这样也可以保证算法是正确的。
    3)区间中点的算法:left + 1/2(right - left); 如果采用1/2(right + left),可能回导致溢出。

    // Forward declaration of isBadVersion API.
    bool isBadVersion(int version);
    
    class Solution {
    public:
        int firstBadVersion(int n) {
            int l = 1, r = n, mid;
            while(l < r){
                mid = l + (r - l) / 2;
                if(isBadVersion(mid)) r = mid;
                else l = mid + 1;
                if(l == r) break;
            }
            return l;
        }
    };
    

    相关文章

      网友评论

          本文标题:2020-02-26 刷题 4 (二叉树,排序和搜索)

          本文链接:https://www.haomeiwen.com/subject/wmbmchtx.html