剑指offer系列刷题

剑指offer！

• 1. 深度优先、广度优先搜索
• • JZ 13 机器人的运动范围
  • JZ 26 树的子结构
  • JZ 27 二叉树的镜像
  • JZ 28 对称的二叉树
  • JZ 34 二叉树中和为某一值的路径

秋招对我好点！

1. 深度优先、广度优先搜索 JZ 13 机器人的运动范围

题目链接
分析： 由于机器可以向右或者向下运动，并且题目求解的是能够到达的格子数，而不是分析运动到右下角会出现的一些问题，因此我们选择广度优先搜索，而不是深度优先搜索。
广度优先搜索类似于二叉树的层次遍历（每次分析上一个节点能达到的所有情况），选择队列queue进行辅助

深度优先搜索由于是递归问题，所以可以使用栈来辅助，递归问题从本质上来说就是利用栈来实现的，这也是为什么递归可以保留上一次递归的信息（先进后出的栈功不可没！）

class Solution {
public:

    int getNum(int x){
        int res = 0;
        while(x!=0){
            res += x%10;
            x/=10;
        }
        return res;
    }

    int movingCount(int m, int n, int k) {
        // 使用广度优先搜索
        // 使用队列来辅助
        if(k==0) return 1;
        queue<pair<int,int>> q;
        vector<vector<int>> visited(m,vector<int>(n,0));
        int ans = 1;
        q.push(make_pair(0,0));
        visited[0][0] = 1;
        int dx[2] = {0,1};
        int dy[2] = {1,0};

        while(!q.empty()){
            auto [x,y] = q.front();
            q.pop();

            // 广度有限搜索
            for(int i=0;i<2;++i){
                int tx = x  + dx[i];
                int ty = y + dy[i];

                if(tx<0 || tx>=m || ty<0 || ty>=n || visited[tx][ty] || getNum(tx) + getNum(ty)>k) continue;
                q.push(make_pair(tx,ty));
                ans++;
                visited[tx][ty] = 1; 
            }
        }

        return ans;
    }
};

JZ 26 树的子结构

题目链接
分析： 对于树的子结构问题，一般都采用递归。
主要步骤有两个：

1. 在树 A 中找到和树 B 的根节点的值一样的节点 p
2. 判断树 A 中以 p 为根节点的子树是不是包含和树 B 一样的结构

/**
 * 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:
    bool isSub(TreeNode* root1, TreeNode* root2){

        if(!root2) return true;
        if(!root1 || root1->val != root2->val) return false;
        return isSub(root1->left,root2->left) && isSub(root1->right,root2->right);
    }
    
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        // 使用递归
        if(!A || !B) return false;   // 如果A B为nullptr的话 返回false

        return isSub(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
};

JZ 27 二叉树的镜像

题目链接
分析： 将root的两个子树先保存下来，一直递归到最深处，进行交换。

/**
 * 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* mirrorTree(TreeNode* root) {

        if(!root) return NULL;

        TreeNode* left = mirrorTree(root->left);
        TreeNode* right = mirrorTree(root->right);

        root->right = left;
        root->left  =right;

        return root;
    }
};

JZ 28 对称的二叉树

题目链接
分析： 如果一棵二叉树和它的镜像一样，那么它是对称的。
因此判断条件可视为 两个树在什么情况下是镜像对称的：

1. 它们的两个根结点具有相同的值
2. 每个树的右子树都与另一个树的左子树镜像对称

/**
 * 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:

    bool check(TreeNode* root1,TreeNode*root2){
        if(!root1 && !root2) return true;
        if(!root1 || !root2) return false;

        return root1->val==root2->val && check(root1->right,root2->left) && check(root2->right,root1->left);
    }
    bool isSymmetric(TreeNode* root) {
        // 根节点有相同的值  并且一个树的左子树和另一棵树的右子树镜像对称
        return check(root,root);
    }
};

JZ 34 二叉树中和为某一值的路径

题目链接
分析： 想都不要想，这题肯定采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。

/**
 * 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 {
private:
    vector<vector<int>> result;
    vector<int> path;

public:
    void dfs(TreeNode* root,int target,int num){
        // 递归结束
        if(!root) return;

        path.push_back(root->val);
        num+=root->val;

        if(!root->left && !root->right && num==target){
            result.push_back(path);
        }

        dfs(root->left, target,num);
        dfs(root->right, target,num);
        path.pop_back();

    }
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        // 使用递归  深度优先搜索
        dfs(root,target,0);
        return result;
    }
};