目录

一、统计有序矩阵中的负数 

暴力数组遍历

二分法

二、搜索二维矩阵 

二分法

三、合并二叉树

深度优先搜索算法

四、填充每个节点的下一个右侧节点指针

 广度优先搜索(层次遍历)

一、统计有序矩阵中的负数 

暴力数组遍历

class Solution {
public:
    int countNegatives(vector>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int ans = 0;
        for(int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if(grid[i][j] < 0){
                    ans += (m - j);
                    break;
                }
            }
        }
        return ans;
    }
};

二分法

class Solution {
public:
    int countNegatives(vector>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int ans = 0;
        for(int i = 0; i < n; i++){
            int low = 0, high = m - 1, flag = -1;
            while(low <= high){
                int mid = low + (high - low) / 2;
                if(grid[i][mid] < 0){
                    flag = mid;
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }
            if(flag > -1) ans += (m - flag);
        }
        return ans;
    }
};

二、搜索二维矩阵 

二分法

class Solution {
public:
    bool searchMatrix(vector>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int low = 0, high = m * n - 1;
        while(low <= high){
            int mid = low + (high - low) / 2;
            if(matrix[mid / n][mid % n] < target){
                low = mid + 1;
            }else if(matrix[mid / n][mid % n] > target){
                high = mid - 1;
            }else{
                return true;
            }
        }
        return false;
    }
};

三、合并二叉树

深度优先搜索算法

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == NULL)
            return root2;
        if(root2 == NULL)
            return root1;
        TreeNode *t3 = new TreeNode(root1->val + root2->val);
        t3->left = mergeTrees(root1->left, root2->left);
        t3->right = mergeTrees(root1->right, root2->right);
        return t3;
    }
};

四、填充每个节点的下一个右侧节点指针

 广度优先搜索(层次遍历)

class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL)
            return root;
        queue q;
        q.push(root);
        while(!q.empty()){
            int n = q.size();
            for(int i = 0; i < n; i++){
                Node *node = q.front();
                q.pop();
                if(i != n - 1){
                    node->next = q.front();
                }
                if(node->left != NULL)
                    q.push(node->left);
                if(node->right != NULL)
                    q.push(node->right);
            }
            
        }
        return root;
    }
};