DFS练习题 ——（上）

DFS

深度优先搜索：一种暴力搜索的算法。

一、二叉树的遍历 — — 中序遍历

题目：

94. 二叉树的中序遍历 - 力扣（LeetCode）

思路：

中序遍历，即每次访问到拐角处进行一次数据的处理，访问的顺序为：

1. 访问左子节点
2. 进行数据的处理
3. 访问右子节点

同理，如果要进行前序遍历，那么顺序为：数据的处理 -> 访问左子节点 -> 访问右子节点

知识回顾：

• ->是用于通过指针访问成员的运算符。
• .是用于直接通过对象访问成员的运算符。
• *有两个用途：解引用指针和创建指针。
• &有两个用途：获取变量的地址和声明引用。

代码实现：

class Solution {
public:
    vector<int> ans;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == nullptr) return {};
        // 向下访问子节点
        inorderTraversal(root -> left);
        ans.push_back(root->val);
        inorderTraversal(root -> right);
        return ans;
    }
};

二、路径总和

题目：

112. 路径总和 - 力扣（LeetCode）

思路：

因为要判断是否存在一条路径（从根节点到叶子节点），其上面的值的和满足目标值，我们因此可以使用深度优先搜索来对每一个节点进行访问，如果访问到根节点就停止，并且判断此时累积的值是否满足目标值。

由于给出的方法框架只有两个参数：树的指针和目标值。此时我们可以进行逆向思考，对目标值做减法，如果有一条路径上所有值能够使目标值等于 0，就说明我们找到了一个合适的路径。

在实现的时候，我们可以遍历左右子树，如果存在一个子树满足目标值，就说明存在该路径，继续向上返回即可。

代码实现：

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return false;
        if(root -> left == nullptr && root -> right == nullptr) return root->val == targetSum;
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};

三、路径总和II

题目：

113. 路径总和 II - 力扣（LeetCode）

思路：

分析题目可知，题目要求我们寻找一条合适的路径，使其满足从根节点到叶子节点，并且路径上的值满足给定的目标值。

思路与 路径总和的思路一样，进行深度搜索，不过单独使用一个二维向量进行记录合适的值。

代码实现：

class Solution {
public:
    vector<vector<int>> ans;
    // tans 向量用于记录每一条路径
    void dfs(TreeNode* root, int targetSum, vector<int> tans){
        if(root == nullptr) return;
        if(root -> right == nullptr && root -> left == nullptr && targetSum == root->val){
            tans.push_back(root -> val);
            ans.push_back(tans);
            return;
        }
        tans.push_back(root -> val);
        dfs(root -> left, targetSum - root -> val, tans);
        dfs(root -> right, targetSum - root -> val, tans);
        return;
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root, targetSum, {});
        return ans;
    }
};

四、恢复二叉树

题目：

99. 恢复二叉搜索树 - 力扣（LeetCode）

思路：

题目说明搜索树中有两个位置错了，要我们将这两个位置恢复成正确的值。

搜索树的性质：

1. 有序性：对于树中的任意节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值。
2. 递归性：二叉搜索树的左子树和右子树本身也是二叉搜索树。
3. 无重复：树中不存在重复的元素。

搜索树的左子节点的值 > 自身的值 > 右子节点的值，我们可以利用这个性质来对二叉搜索树进行遍历 —— 中序遍历。

• 首先对二叉搜索树进行一次中序遍历，得到正确的顺序数组。
• 对得到的顺序数组进行检查，判断是否存在顺序不正确的节点（严格的递减），找到错误的节点的位置。
• 再次遍历二叉树，对错误的节点尽心位置交换。

对数组进行检查，这里需要考虑到两种情况：

1. 交换的两个位置相邻：直接记录 i 和 i + 1 即可。
2. 交换的两个位置不相邻 ：第一次记录异常值 i，然后对第二个值不断向后寻找（如：1，2，3 因为目的是使数组严格递增，所以首先找到异常值 1 和 2，记录位置 0 和 1，然后继续向后寻找，2 和 3 也是异常的，此时只更新第二个值即可，记录位置更新为 0 和 2，所以只需要对 0 和 1这两个位置进行交换即可）。

代码实现：

class Solution {
public:
    vector<int> ans;
    void dfs(TreeNode* root) {
        if(root == nullptr) return;
        // 前序遍历
        dfs(root -> left);
        ans.push_back(root -> val);
        dfs(root -> right);
        return;
    }
    // 寻找错误的位置
    pair<int, int> find(vector<int>& nums) {
        int n = nums.size();
        int per = -1, next = -1;
        for(int i = 0;i < n - 1;i ++) {
            if(nums[i + 1] < nums[i]){
                next = i + 1;
                if(per == -1){
                    per = i;
                } else break;
            }
        }
        int x = nums[per], y = nums[next];
        return {x, y};
    }
    void recover(TreeNode* root, int count, int x, int y) {
        if(root == nullptr) return;
        if(root -> val == x || root -> val == y) {
            root -> val = root->val == x? y: x;
            if(--count == 0) return ;
        }
        recover(root->left, count, x, y);
        recover(root->right, count, x, y);
    }
    void recoverTree(TreeNode* root) {
        // 遍历两个数组
        dfs(root);
        pair<int, int> p = find(ans);
        recover(root, 2, p.first, p.second);
    }
};

五、全排列

题目：

46. 全排列 - 力扣（LeetCode）

思路:

这道题需要找出所有全排列的结果，可以使用DFS进行暴力的搜索每一个答案。最简单的思路：第一个位置可能是所有值，因此进行一次遍历，得到所有值在第一个位置的可能（此时需要进行将原位置上的数与需要在该位置的树进行一次交换，因为如果第一个位置不是原来的值，那么原来的值一定在之后的某个位置上），第二个位置也是如此，第三个位置也是如此…，使用一个计数器进行计数，如果排列的长度满足就存入到二维数组中，并进行返回。

本质上，该算法是按照位置进行确定每一个可能的值的，最后形成了一个树结构。

代码实现：

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(vector<int>& nums, int pos){
        if(pos == nums.size() - 1){
            ans.push_back(nums);
            return;
        }
        for(int i = pos;i < nums.size();i ++){
            swap(nums[i], nums[pos]);
            dfs(nums, pos + 1);
            swap(nums[i], nums[pos]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }
};

六、全排列II

题目：

LCR 084. 全排列 II - 力扣（LeetCode）

思路：

这一题是寻找出不重复的全排列，也就是说给出的原始的值中，至少存在相同的两个值，思路与全排列一致，需要另行判断某个值是否重复了。

由于是针对每一个位置存放值的，因此可以添加一个判断条件，该值是否在之前已经存放过了，也就是说，在该值之前，是否已经有一个与之相同的值放入到了该位置上。

代码实现：

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(vector<int>& nums, int pos){
        if(pos == nums.size() - 1){
            ans.push_back(nums);
            return;
        }
        for(int i = pos; i < nums.size();i ++){
            // 判断是否已经交换过了
            bool flag = false;
            for(int j = pos; j < i; j ++){
                if(nums[j] == nums[i]) flag = true;
            }
            if(!flag){
                swap(nums[i], nums[pos]);
                dfs(nums, pos + 1);
                swap(nums[i], nums[pos]);
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }
};

全排列参考文章：全排列问题

七、水壶问题

题目：

365. 水壶问题 - 力扣（LeetCode）

思路：

分析题目可得，只有六种状态：

1. 倒空水壶 x
2. 倒空水壶 y
3. 倒满水壶 x
4. 倒满水壶 y
5. 将水壶 x倒入水壶 y
6. 将水壶 y倒入水壶 x

一个最简单的思路：使用DFS进行模拟，由于没有一个最终的状态，因此需要使用一个集合来记录出现的所有状态，如果某个状态出现过了，就直接返回false，避免陷入无限执行中。

代码实现：

class Solution {
public:
    set<pair<int, int>> repeat;

    bool dfs(int x, int y, int idx, int idy, int target) {
        if (idx + idy == target) return true;

        // 判断是否已经存在过了
        if (repeat.find({idx, idy}) != repeat.end()) return false;
        repeat.insert({idx, idy});

        // 三种状态：倒满任意一个水壶、倒空任意一个水壶、将一个水壶导入另一个水壶中
        // 倒满
        if (dfs(x, y, x, idy, target)) return true;
        if (dfs(x, y, idx, y, target)) return true;
        // 倒空
        if (dfs(x, y, 0, idy, target)) return true;
        if (dfs(x, y, idx, 0, target)) return true;
        // y 倒入 x
        int empty_x = x - idx;
        int empty_y = y - idy;
        if (dfs(x, y, idx + min(empty_x, idy), idy - min(empty_x, idy), target)) return true;
        // x 倒入 y
        if (dfs(x, y, idx - min(empty_y, idx), idy + min(empty_y, idy), target)) return true;

        return false;
    }

    bool canMeasureWater(int x, int y, int target) {
        if (x + y < target) return false;
        if (x == target || y == target || x + y == target) return true;
        return dfs(x, y, x, y, target);
    }
};