41 篇博文 含有标签「深度优先搜索」

1、题干​

给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

提醒一下， 二叉搜索树 满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

提示：

• 树中的节点数在 [1, 100] 范围内。
• 0 <= Node.val <= 100
• 树中的所有值均 不重复 。

注意：该题目与 538: https://leetcode-cn.com/problems/convert-bst-to-greater-tree/  相同

2、思路​

根据题意使用DFS模拟，需要注意：

• 对左子节点求和，需要将父节点求和结果、右子树节点之和、自身数值3者累加
• 对右子节点求和，需要将右边祖先节点求和结果、右子树节点之和、自身数值3者累加

3、代码​

function bstToGst(root: TreeNode | null): TreeNode | null {
    return dfs(root), root;
}

function dfs(root?: TreeNode, pSum = 0): number {
    if (!root) return 0;

    const val = root.val;
    const rSum = dfs(root.right, pSum);
    root.val = val + pSum + rSum;
    const lSum = dfs(root.left, root.val);

    return val + rSum + lSum;
}

1、题干​

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

• 两棵树上的节点数目都在范围 [0, 100] 内
• -104 <= Node.val <= 104

2、思路​

DFS 判断两棵树当前节点值是否相等，左右子树是否相等

3、代码​

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if (p && q) return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

    return !p && !q;
};

1、题干​

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

示例 1：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

示例 2：

输入：root = []
输出：[]

提示：

• 树中的节点数在范围 [0, 6000] 内
• -100 <= Node.val <= 100

进阶：

• 你只能使用常量级额外空间。
• 使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。

2、思路​

BFS模拟，每一层的节点用一个队列存储，队列中节点的 next 指向下一个节点即可。

这题没有 Rust 编码环境。。

3、代码​

function connect(root: Node | null): Node | null {
    let queue: Node[] = root ? [root] : [];

    while (queue.length) {
        const nextQueue = [];
        for (let i = 0; i < queue.length; i++) {
            queue[i].next = queue[i + 1];
            if (queue[i].left) nextQueue.push(queue[i].left);
            if (queue[i].right) nextQueue.push(queue[i].right);
        }
        queue = nextQueue;
    }

    return root;
};

1、题干​

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

示例 1：

输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

示例 2：

输入：root = [1,null,2,null,0,3]
输出：3

提示：

• 树中的节点数在 2 到 5000 之间。
• 0 <= Node.val <= 105

2、思路​

递归求子孙节点的最小值与最大值，分别求最大值最小值与当前节点值的差的绝对值，比较得出最大差值。

3、代码​

function maxAncestorDiff(root: TreeNode | null): number {
    let ans = -Infinity;

    function dfs(node: TreeNode) {
        if (!node) return [Infinity, -Infinity];
        if (!node.left && !node.right) return [node.val, node.val];

        const r1 = dfs(node.left);
        const r2 = dfs(node.right);

        const min = Math.min(r1[0], r2[0]);
        const max = Math.max(r1[1], r2[1]);

        ans = Math.max(ans, Math.abs(node.val - min), Math.abs(node.val - max));

        return [Math.min(min, node.val), Math.max(max, node.val)];
    }

    return dfs(root), ans;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

骑士在一张 n x n 的棋盘上巡视。在 有效 的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次 。

给你一个 n x n 的整数矩阵 grid ，由范围 [0, n * n - 1] 内的不同整数组成，其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。

如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。

注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。

示例 1：

输入：grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
输出：true
解释：grid 如上图所示，可以证明这是一个有效的巡视方案。

示例 2：

输入：grid = [[0,3,6],[5,8,1],[2,7,4]]
输出：false
解释：grid 如上图所示，考虑到骑士第 7 次行动后的位置，第 8 次行动是无效的。

提示：

• n == grid.length == grid[i].length
• 3 <= n <= 7
• 0 <= grid[row][col] < n * n
• grid 中的所有整数 互不相同

2、思路​

从左上角开始 DFS 遍历，如果能完成遍历则说明巡视方案有效

3、代码​

function checkValidGrid(grid: number[][]): boolean {
    let vis = 0;
    const dirs = [[-2, -1], [2, 1], [-2, 1], [2, -1], [-1, -2], [1, 2], [-1, 2], [1, -2]];
    const t = grid.length * grid[0].length;

    function dfs(r: number, c: number) {
        vis++;
        if (grid[r][c] === t - 1) return;

        for (const [dr, dc] of dirs) {
            if (grid[r + dr]?.at(c + dc) === grid[r][c] + 1) {
                dfs(r + dr, c + dc);
                break;
            }
        }
    }

    dfs(0, 0);

    return vis === t;
};

4、复杂度​

• 时间复杂度： $O(n^2)$
• 空间复杂度： $O(n^2)$

5、执行结果​

1、题干​

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。

• 例如，"/leetcode" 和 "/leetcode/problems" 都是有效的路径，而空字符串和 "/" 不是。

示例 1：

输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释："/a/b" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。

示例 2：

输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d" 都会被删除，因为它们都是 "/a" 的子文件夹。

示例 3：

输入: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
输出: ["/a/b/c","/a/b/ca","/a/b/d"]

提示：

• 1 <= folder.length <= 4 * 104
• 2 <= folder[i].length <= 100
• folder[i] 只包含小写字母和 '/'
• folder[i] 总是以字符 '/' 起始
• folder 每个元素都是 唯一 的

2、思路1-排序​

• 对文件夹数组 folder 升序排序，初始化父文件夹 pf = folder[0] + '/'
• 遍历检查所有文件夹 folder[i] 与当前父文件夹 pf 是否父子关系，是则说明 folder[i] 是子文件夹，不是则将 folder[i] 置为父文件夹继续检查

3、代码​

function removeSubfolders(folder: string[]): string[] {
    folder.sort();

    const ans = [folder[0]];
    let pf = folder[0] + '/';

    for (let i = 1; i < folder.length; i++) {
        if (!folder[i].startsWith(pf)) {
            ans.push(folder[i]);
            pf = folder[i] + '/';
        }
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(nm*logn)$
• 空间复杂度：$O(logn)$

5、执行结果​

6、思路2-哈希​

将 folder 数组中所有文件夹存入哈希集合 set，遍历检查文件夹 folder[i] 所有前缀路径，若前缀路径存在于 set 中，则说明 folder[i] 是子文件夹

7、代码​

function removeSubfolders(folder: string[]): string[] {
    const ans = [], set = new Set(folder);

    for (const f of folder) {
        let found = false;

        for (let i = 0; i < f.length;) {
            i = f.indexOf('/', i + 1);
            if (i < 0) break;

            const dir = f.slice(0, i);

            if (set.has(dir)) {
                found = true;
                break;
            }
        }

        if (!found) ans.push(f);
    }

    return ans;
};

8、复杂度​

• 时间复杂度：$O(nm)$
• 空间复杂度：$O(nm)$

9、执行结果​

1、题干​

给你一棵 完整二叉树 的根，这棵树有以下特征：

• 叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
• 非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。

计算 一个节点的值方式如下：

• 如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。
• 否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。

返回根节点 root 的布尔运算值。

完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。

叶子节点 是没有孩子的节点。

示例 1：

输入：root = [2,1,3,null,null,0,1]
输出：true
解释：上图展示了计算过程。
AND 与运算节点的值为 False AND True = False 。
OR 运算节点的值为 True OR False = True 。
根节点的值为 True ，所以我们返回 true 。

示例 2：

输入：root = [0]
输出：false
解释：根节点是叶子节点，且值为 false，所以我们返回 false 。

提示：

• 树中节点数目在 [1, 1000] 之间。
• 0 <= Node.val <= 3
• 每个节点的孩子数为 0 或 2 。
• 叶子节点的值为 0 或 1 。
• 非叶子节点的值为 2 或 3 。

2、思路​

使用 DFS 模拟

3、代码​

function evaluateTree(root: TreeNode | null): boolean {
    if (!root || (!root.left && !root.right)) return !!root?.val;

    const l = evaluateTree(root.left);
    const r = evaluateTree(root.right);

    return root.val === 2 ? (l || r) : (l && r);
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。

最开始时：

• 「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）；
• 「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x。

「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色。

之后两位玩家轮流进行操作，「一号」玩家先手。每一回合，玩家选择一个被他染过色的节点，将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色（「一号」玩家染红色，「二号」玩家染蓝色）。

如果（且仅在此种情况下）当前玩家无法找到这样的节点来染色时，其回合就会被跳过。

若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。

现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个 y 值可以确保你赢得这场游戏，则返回 true ；若无法获胜，就请返回 false 。

示例 1 ：

输入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
输出：true
解释：第二个玩家可以选择值为 2 的节点。

示例 2 ：

输入：root = [1,2,3], n = 3, x = 1
输出：false

提示：

• 树中节点数目为 n
• 1 <= x <= n <= 100
• n 是奇数
• 1 <= Node.val <= n
• 树中所有值 互不相同

还好不是博弈论

2、思路​

DFS 求出整棵树的节点总数 c 和节点 x 的左右子树的节点总数 cl 、cr，继而可以求得 x 子树之外的节点总数 c - cl - cr - 1，3者中的最大值如果超过节点总数的一半 c/2，则必定存在必胜值 y

3、代码​

function btreeGameWinningMove(root: TreeNode | null, n: number, x: number): boolean {
    let cl = 0, cr = 0;

    function dfs(node: TreeNode) {
        if (!node) return 0;

        const c1 = dfs(node.left);
        const c2 = dfs(node.right);

        if (node.val === x) cl = c1, cr = c2;

        return c1 + c2 + 1;
    }

    const c = dfs(root);

    return Math.max(c - cl - cr - 1, cl, cr) > c / 2;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位都是范围 [0, k - 1] 中的一个数字。

保险箱有一种特殊的密码校验方法，你可以随意输入密码序列，保险箱会自动记住 最后 n 位输入 ，如果匹配，则能够打开保险箱。

• 例如，正确的密码是 "345" ，并且你输入的是 "012345" ：
  • 输入 0 之后，最后 3 位输入是 "0" ，不正确。
  • 输入 1 之后，最后 3 位输入是 "01" ，不正确。
  • 输入 2 之后，最后 3 位输入是 "012" ，不正确。
  • 输入 3 之后，最后 3 位输入是 "123" ，不正确。
  • 输入 4 之后，最后 3 位输入是 "234" ，不正确。
  • 输入 5 之后，最后 3 位输入是 "345" ，正确，打开保险箱。

在只知道密码位数 n 和范围边界 k 的前提下，请你找出并返回确保在输入的 某个时刻 能够打开保险箱的任一 最短 密码序列 。

示例 1：

输入：n = 1, k = 2
输出："10"
解释：密码只有 1 位，所以输入每一位就可以。"01" 也能够确保打开保险箱。

示例 2：

输入：n = 2, k = 2
输出："01100"
解释：对于每种可能的密码：
- "00" 从第 4 位开始输入。
- "01" 从第 1 位开始输入。
- "10" 从第 3 位开始输入。
- "11" 从第 2 位开始输入。
因此 "01100" 可以确保打开保险箱。"01100"、"10011" 和 "11001" 也可以确保打开保险箱。

提示：

• 1 <= n <= 4
• 1 <= k <= 10
• 1 <= kn <= 4096

2、思路1​

• 题意

题目要找一个能打开保险箱的最短字符串，实际是想找一个所有密码组合而成的最短字符串，该字符串的特征是：截取其中任意长度为 n 的字符串都是保险箱的密码。

• 思路

先找出所有密码串，再用所有密码串组合出最短字符串。

找出所有密码时要注意，任一密码串长度都为 n，每一位的取值范围是 $[0,k-1]$。

组合最短字符串时要注意，在组合任意两个密码串 a 和 b 时，必须满足 a 剔除首位字符后与 b 剔除末位字符后相等。举个例子：

• 012 与 123 可以组合，因为 012 剔除首位后与 123 剔除末位后都是 12
• 012 与 213 则不能组合

• 代码主要逻辑：
  • 先找出所有可能的密码串 pwds
  • 将所有密码串按前缀分组存入哈希表 pwdMap，前缀指的是剔除密码末位字符之后的字符串
  • 使用回溯组合所有密码串
  • 所有密码串都用完则顺序拼接并返回

3、代码​

function crackSafe(n: number, k: number): string {
    if (k === 1) return '0'.padStart(n, '0');

    // 生成pwds
    const pwds = new Array(k ** n).fill('0').map((v, i) => {
        return k < 2 ? v : i.toString(k).padStart(n, "0");
    });

    if (n === 1) return pwds.join('');

    const pwdMap = new Map();
    for (const p of pwds) {
        const prefix = p.slice(0, n - 1);
        if (!pwdMap.has(prefix)) pwdMap.set(prefix, []);
        pwdMap.get(prefix).push(p);
    }

    // 组合pwds
    let ans = '';
    function dfs(cur: string, used: Set<string>) {
        if (ans) return;
        if (used.size === pwds.length) {
            const nums = [...used];
            ans = nums[0] + nums.slice(1).map(w => w.slice(-1)).join('');
            return;
        }

        const nums = pwdMap.get(cur.slice(1));
        for (const n of nums) {
            if (used.has(n)) continue;
            used.add(n);
            dfs(n, used);
            used.delete(n);
        }
    }

    for (const p of pwds) dfs(p, new Set([p]));

    return ans;
}

4、复杂度​

• 时间复杂度：$O(k*k^{2n})$
• 空间复杂度：$O(k*k^{2n})$

5、执行结果​

6、思路2​

这是思路1的优化版，时间复杂度更低。主要是猜测以任意密码开头都有可能找到最短字符串，因此枚举时只取第一个密码作为起点构造字符串。代码的不同表现在倒数第二行，移除了遍历，只取第一个密码 pwds[0] 进行回溯。

7、代码​

function crackSafe(n: number, k: number): string {
    if (k === 1) return '0'.padStart(n, '0');

    // 生成pwds
    const pwds = new Array(k ** n).fill('0').map((v, i) => {
        return k < 2 ? v : i.toString(k).padStart(n, "0");
    });

    if (n === 1) return pwds.join('');

    const pwdMap = new Map();
    for (const p of pwds) {
        const prefix = p.slice(0, n - 1);
        if (!pwdMap.has(prefix)) pwdMap.set(prefix, []);
        pwdMap.get(prefix).push(p);
    }

    // 组合pwds
    let ans = '';
    function dfs(cur: string, used: Set<string>) {
        if (ans) return;
        if (used.size === pwds.length) {
            const nums = [...used];
            ans = nums[0] + nums.slice(1).map(w => w.slice(-1)).join('');
            return;
        }

        const nums = pwdMap.get(cur.slice(1));
        for (const n of nums) {
            if (used.has(n)) continue;
            used.add(n);
            dfs(n, used);
            used.delete(n);
        }
    }

    dfs(pwds[0], new Set([pwds[0]]));

    return ans;
}

8、复杂度​

• 时间复杂度：$O(k*k^n)$
• 空间复杂度：$O(k*k^n)$

9、执行结果​

1、题干​

用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。

箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。

• 将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
• 将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。

在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。

返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。

示例 1：

输入：grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
输出：[1,-1,-1,-1,-1]
解释：示例如图：
b0 球开始放在第 0 列上，最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。
b2 球开始放在第 2 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b3 球开始放在第 3 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b4 球开始放在第 4 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。

示例 2：

输入：grid = [[-1]]
输出：[-1]
解释：球被卡在箱子左侧边上。

示例 3：

输入：grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]
输出：[0,1,2,3,4,-1]

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• grid[i][j] 为 1 或 -1

2、解题思路​

按题意模拟

3、代码​

var findBall = function (grid) {
    const res = [], m = grid.length, n = grid[0].length;

    for (let j = 0; j < n; j++) {
        let k = j;
        for (let i = 0; i < m; i++) {
            if (grid[i][k] === 1 && grid[i][k] === grid[i][k + 1]) k++;
            else if (grid[i][k] === -1 && grid[i][k] === grid[i][k - 1]) k--;
            else res[j] = -1;
        }
        if (res[j] === undefined) res[j] = k;
    }

    return res;
};

4、执行结果​