2020-02-26 刷题 4 （二叉树，排序和搜索）

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;
    }
};