DFS练习题 ——(上)

发布于:2024-11-28 ⋅ 阅读:(35) ⋅ 点赞:(0)

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. 交换的两个位置相邻:直接记录 ii + 1 即可。
  2. 交换的两个位置不相邻 :第一次记录异常值 i,然后对第二个值不断向后寻找(如:1,2,3 因为目的是使数组严格递增,所以首先找到异常值 1 和 2,记录位置 0 和 1,然后继续向后寻找,2 和 3 也是异常的,此时只更新第二个值即可,记录位置更新为 0 和 2,所以只需要对 01这两个位置进行交换即可)。

代码实现:

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