题目链接：二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

方法一：层序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;
        queue<TreeNode*> q;
        q.push(root);
        int num = 0;
        while (q.size()) {
            int t = q.size();
            //int num;
            while (t--) {
                TreeNode* tmp = q.front();
                q.pop();
                num = tmp->val;
                if (tmp->left != nullptr) q.push(tmp->left);
                if (tmp->right != nullptr) q.push(tmp->right);
            }
            ans.push_back(num);
        }
        return ans;
    }
};

方法二：bfs

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if (!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            int size = q.size();
            ans.push_back(q.front()->val);
            for (int i = 0;i < size;i++) {
                TreeNode* node = q.front();
                q.pop();
                if (node->right) q.push(node->right);
                if (node->left) q.push(node->left);
            }
        }
        return ans;
    }
};

方法三：dfs

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root,int depth,vector<int>& ans) {
        if (root == nullptr) return ;
        if (depth == ans.size()) ans.push_back(root->val);
        dfs(root->right,depth+1,ans);
        dfs(root->left,depth+1,ans);
    }
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        dfs(root,0,ans);
        return ans;
    }
};

题目链接：对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

方法一：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode* l,TreeNode* r) {
        if (!l && !r) return true;
        if (!l || !r) return false;
        return l->val == r->val && check(l->left,r->right) && check(l->right,r->left);
    }
    bool isSymmetric(TreeNode* root) {
        return check(root->left,root->right);
    }
};

题目链接：分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

方法一：动态规划+二维数组

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        vector dp(nums.size() + 1, vector<int> (2e4 + 10, 0));
        double sum = 0;
        for (auto x : nums) {
            sum += x;
        }
        double target = sum / 2;
        for (int i = 0;i < nums.size();i++) {
            for (int j = 0;j <= target;j++) {
                if (j < nums[i]) {
                    dp[i+1][j] = dp[i][j];
                }else 
                    dp[i + 1][j] = max(dp[i][j], dp[i][j - nums[i]] + nums[i]);
            }
        }
        return dp[nums.size()][target] == target;
    }
};

方法二：动态规划+一维数组

//一维优化
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        vector<int> dp(2e4 + 10, 0);
        double sum = 0;
        for(int i = 0;i < nums.size(); ++i)
            sum += nums[i];
        double target = double(sum / 2);

        for(int i = 0; i < nums.size(); ++i)
            for(int j = target;j >= nums[i]; --j)
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        
        return dp[target] == target;
    }
};

题目链接：N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

方法一：回溯

class Solution {
public:
    vector<vector<string>> ans;
    int m[15][15];
    bool check(int x,int y,int n) {
        for (int i = 0;i < x;i++) {
            if (m[i][y]) return false;
        }
        for (int i = 0;i < y;i++) {
            if (m[x][i]) return false;
        }
        int num = min(x,y);
        // 左上
        for (int i = 1;i <= num;i++) {
            if (m[x-i][y-i]) return false;
        }
        num = min(x,n-y);
        //右上
        for (int i = 1;i <= num;i++) {
            if (m[x-i][y+i]) return false;
        }
        num = min(n-x,n-y);
        
        return true;
    }
    void f(int n,int x) {
        if (x >= n) {
            vector<string> t;
            for (int i = 0;i < n;i++) {
                string s = "";
                for (int j = 0;j < n;j++) {
                    if (m[i][j] == 1) {
                        s += "Q";
                    }else {
                        s += ".";
                    }
                }
                t.push_back(s);
            }
            ans.push_back(t);
            return ;
        }
        for (int i = 0;i < n;i++) {
            if (check(x,i,n)) {
                m[x][i] = 1;
                f(n,x+1);
                m[x][i] = 0;
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        f(n,0);
        return ans;
    }
}; 

题目链接：单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

方法一：回溯

class Solution {
public:
    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    bool visited[20][20];
    bool ans = false;
    void dfs(vector<vector<char>>& board, string word,int x,int y,int t) {
        if (t >= word.size()) {
            ans = true;
            return ;
        }
        if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || visited[x][y]) return;
        if (board[x][y] != word[t]) return ;
        visited[x][y] = true;
        for (int i = 0;i < 4;i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            
            dfs(board,word,tx,ty,t+1);
        }
        visited[x][y] = false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0;i < board.size();i++) {
            for (int j = 0;j < board[0].size();j++) {
                dfs(board,word,i,j,0);
            }
        }
        return ans;
    }
};