25 篇博文 含有标签「广度优先搜索」

1、题干​

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

示例 1：

输入: edges = [[1,2],[1,3],[2,3]]
输出: [2,3]

示例 2：

输入: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
输出: [1,4]

提示:

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ai < bi <= edges.length
• ai != bi
• edges 中无重复元素
• 给定的图是连通的 

并查集还没学会，只能先用树和图的思想解题

2、解题思路​

在树的概念中，叶子结点是指没有子结点的结点，叶子节点只跟父节点存在关联，即只有1条边。如果某个节点下只有叶子节点，把该节点下的所有叶子节点都移除掉之后它自己就变成了叶子节点。如果循环往复地移除树的所有叶子节点，最终这棵树的节点数会变为0 。

如果按题目意思在树中添加一条边，这棵树会变成一个有环图，而在移除所有叶子节点的操作中，环上的所有节点都不会被移除，本题就是利用这个结论解题。

总体思路 ：循环往复地移除树上所有的叶子节点，直到不存在叶子节点，最后遍历找到环中最后出现的边。

大体步骤 ：

• 先用矩阵建立节点关联关系，记为 matrix
  • matrix 是一维数组，下标表示节点值
  • matrix 中的元素是哈希集合，集合中包含与当前节点关联的所有节点
• 遍历 matrix 并把当前节点加入队列 queue 中，进行叶子节点的判断与移除
  • 若该节点是叶子节点，则双向移除该节点与父节点的关联关系，同时把父节点加入队列 queue 中进行下一轮处理
  • 若该节点不是叶子节点则跳过
• 最后遍历二维数组 edges 并在 matrix 中查找出处于环上且序号最大的边

3、代码​

var findRedundantConnection = function (edges) {
    const n = edges.length, matrix = new Array(n + 1).fill(0);

    for (const [i, j] of edges) {
        !matrix[i] ? (matrix[i] = new Set([j])) : matrix[i].add(j);
        !matrix[j] ? (matrix[j] = new Set([i])) : matrix[j].add(i);
    }

    for (let k = 1; k <= n; k++) {
        const queue = [k];

        for (const i of queue) {
            if (matrix[i].size !== 1) continue;

            const j = matrix[i].keys().next().value;
            matrix[i].delete(j), matrix[j].delete(i);
            queue.push(j);
        }
    }

    return edges.reduce((a, [i, j]) => (matrix[i].size > 1 && matrix[j].size > 1 ? [i, j] : a), null);
};

4、复杂度​

• 时间复杂度：$O(nlogn)$，复杂度比较高的代码在双层循环剪叶子那一段，外层循环 $n$ 次，内层循环最多为树的高度 $logn$ 次
• 空间复杂度：$O(n)$

5、执行结果​

• 执行用时: 68 ms
• 内存消耗: 42.1 MB

1、题干​

城市用一个 双向连通 图表示，图中有 n 个节点，从 1 到 n 编号（包含 1 和 n）。图中的边用一个二维整数数组 edges 表示，其中每个 edges[i] = [ui, vi] 表示一条节点 ui 和节点 vi 之间的双向连通边。每组节点对由 最多一条 边连通，顶点不存在连接到自身的边。穿过任意一条边的时间是 time 分钟。

每个节点都有一个交通信号灯，每 change 分钟改变一次，从绿色变成红色，再由红色变成绿色，循环往复。所有信号灯都 同时 改变。你可以在 任何时候 进入某个节点，但是 只能 在节点 信号灯是绿色时 才能离开。如果信号灯是  绿色 ，你 不能 在节点等待，必须离开。

第二小的值 是 严格大于 最小值的所有值中最小的值。

• 例如，[2, 3, 4] 中第二小的值是 3 ，而 [2, 2, 4] 中第二小的值是 4 。

给你 n、edges、time 和 change ，返回从节点 1 到节点 n 需要的 第二短时间 。

注意：

• 你可以 任意次 穿过任意顶点，包括 1 和 n 。
• 你可以假设在 启程时 ，所有信号灯刚刚变成 绿色 。

示例 1：

输入：n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
输出：13
解释：
上面的左图展现了给出的城市交通图。
右图中的蓝色路径是最短时间路径。
花费的时间是：
- 从节点 1 开始，总花费时间=0
- 1 -> 4：3 分钟，总花费时间=3
- 4 -> 5：3 分钟，总花费时间=6
因此需要的最小时间是 6 分钟。

右图中的红色路径是第二短时间路径。
- 从节点 1 开始，总花费时间=0
- 1 -> 3：3 分钟，总花费时间=3
- 3 -> 4：3 分钟，总花费时间=6
- 在节点 4 等待 4 分钟，总花费时间=10
- 4 -> 5：3 分钟，总花费时间=13
因此第二短时间是 13 分钟。      

示例 2：

输入：n = 2, edges = [[1,2]], time = 3, change = 2
输出：11
解释：
最短时间路径是 1 -> 2 ，总花费时间 = 3 分钟
第二短时间路径是 1 -> 2 -> 1 -> 2 ，总花费时间 = 11 分钟

提示：

• 2 <= n <= 104
• n - 1 <= edges.length <= min(2 * 104, n * (n - 1) / 2)
• edges[i].length == 2
• 1 <= ui, vi <= n
• ui != vi
• 不含重复边
• 每个节点都可以从其他节点直接或者间接到达
• 1 <= time, change <= 103

2、解题思路​

• 将路径数组 edges 转为邻接矩阵便于后续搜索
  • 转换过程中注意本题是双向连通图，任意边上的两个点都可以作为出发点
• 利用BFS求最短路径步数 min1 和次短路径步数 min2，BFS过程中需要注意剪枝：
  • 剪枝1：若 min2 已经找到则退出
  • 剪枝2：若从当前节点到达下一节点的步数 step+1 与到达下一节点的最小步数 minSteps.get(k) 之差不小于2 step + 1 - minSteps.get(k) >= 2，则跳过
  • 剪枝3：同一层级每个节点只出现一次
• 按最短路径逐步叠加通过时间和等待红灯时间

这里剪枝的主要方式跟大多数题解不太一样，大部分题解都是利用节点不可能访问超过2次作为主要剪枝方式，确实没有想到这个点；这里主要利用次短路径与最短路径步数差值不超过2进行剪枝，原因是最短路径在任意节点上重复一个来回只需要2步，若次短路径的步数比最短路径多2步以上则说明其不能成为次短。

3、代码​

var secondMinimum = function (n, edges, time, change) {
    edges = edges.reduce((a, c) => {
        // 双向连通图，建表时两个都可以作为出发点
        !a[c[0]] ? (a[c[0]] = [c[1]]) : a[c[0]].push(c[1]);
        !a[c[1]] ? (a[c[1]] = [c[0]]) : a[c[1]].push(c[0]);
        return a;
    }, new Array(n + 1));

    let min1 = Infinity, min2 = Infinity, nodes = new Set([1]), step = 1;
    const minSteps = new Map();

    while (nodes.size && min2 === Infinity) {
        const nextNodes = new Set();
        for (const i of nodes) {
            minSteps.set(i, step);
            if (i === n) min1 === Infinity || min1 === step ? (min1 = step) : (min2 = step);
            for (const k of edges[i]) {
                if (minSteps.has(k) && step + 1 - minSteps.get(k) >= 2) continue;
                nextNodes.add(k);
            }
        }

        step++;
        nodes = nextNodes;
    }

    let cost = 0;
    for (let i = 1; i < Math.min(min1 + 2, min2); i++) {
        if (((cost / change) >> 0) % 2) cost += change - (cost % change);
        cost += time;
    }

    return cost;
};

4、执行结果​

• 执行用时: 400 ms
• 内存消耗: 66.9 MB

1、题干​

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：

• i + 1 需满足：i + 1 < arr.length
• i - 1 需满足：i - 1 >= 0
• j 需满足：arr[i] == arr[j] 且 i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

示例 1：

输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。

示例 2：

输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。

示例 3：

输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。

提示：

• 1 <= arr.length <= 5 * 104
• -108 <= arr[i] <= 108

DFS解法写自闭了，简单写下BFS和动态规划的思路和代码

2、解法1-BFS​

BFS解法需要注意各种边界条件以及剪枝优化，不然很可能超时、内存溢出。剪枝的方法有这些：

• 跳过相邻且值相同的节点，只留头尾，中间部分没有意义
• 跳过已访问过的节点
• BFS的当前层级超过到达该节点的最小步数

3、代码​

var minJumps = function (arr) {
    const n = arr.length;

    // 记录数字对应的索引以及最小步数
    const map = new Map();
    for (let i = 0; i < n; i++) {
        if (arr[i] === arr[i + 1] && arr[i] === arr[i - 1]) continue;
        map.get(arr[i]) ? map.get(arr[i])[0].push(i) : map.set(arr[i], [[i], Infinity]);
    }

    const visited = new Set();
    let queue = [0], level = 0, res = Infinity;

    while (queue.length) {
        const set = new Set();
        if (level >= res) break;
        for (const i of queue) {
            if (visited.has(i)) continue;
            visited.add(i);

            if (i === n - 1) res = Math.min(res, level);
            if (i >= 1) set.add(i - 1);
            if (i <= n - 2) set.add(i + 1);

            const [idxs, min] = map.get(arr[i]);
            if (level + 1 > min) continue;

            map.get(arr[i])[1] = Math.min(min, level + 1);
            for (const x of idxs) {
                if (x !== i) set.add(x);
            }
        }
        queue = [...set];
        level++;
    }

    return res;
};

4、执行结果​

• 执行用时: 180 ms
• 内存消耗: 62.3 MB

5、解法2-动态规划​

实际上这道题不能用动态规划，因为违反了无后效性，其实带来的问题就是不能一次性规划出结果，这个问题没啥好办法，多规几次就出来了（两次动态规划结果一致则认为已经是最优解）。

6、代码​

var minJumps = function (arr) {
    const n = arr.length;

    // 记录数字对应的索引
    const map = new Map();
    for (let i = 0; i < n; i++) {
        map.get(arr[i]) ? map.get(arr[i])[0].push(i) : map.set(arr[i], [[i], Infinity]);
    }

    // DP处理
    const dp = new Array(n).fill(Infinity);
    dp[0] = 0;

    function updateSame(i) {
        const [idxs, min] = map.get(arr[i]);
        if (idxs.length < 2 || dp[i] >= min) return;
        map.get(arr[i])[1] = dp[i];
        for (let j = 0; j < idxs.length; j++) {
            dp[idxs[j]] = Math.min(dp[i] + 1, dp[idxs[j]]);
        }
    }

    function runDp() {
        for (let i = 0; i < n; i++) {
            if (i > 0) dp[i - 1] = Math.min(dp[i] + 1, dp[i - 1]), updateSame(i - 1);
            if (i < n - 1) dp[i + 1] = Math.min(dp[i] + 1, dp[i + 1]), updateSame(i + 1);

            updateSame(i);
        }
    }

    while (1) {
        runDp();
        const r1 = dp.toString();
        runDp();
        const r2 = dp.toString();
        if (r1 === r2) return dp[n - 1];
    }
};

7、执行结果​

• 执行用时: 380 ms
• 内存消耗: 65.1 MB

8、解法3-DFS​

各种处理和优化，最终还是没能AC，直接贴代码吧，如果有大神看到希望指点下🙏

var minJumps = function (arr) {
    const n = arr.length;

    // 记录数字对应的索引以及最小步数
    const map = new Map();
    for (let i = 0; i < n; i++) {
        if (arr[i] === arr[i + 1] && arr[i] === arr[i - 1]) continue;
        map.get(arr[i]) ? map.get(arr[i])[0].push(i) : map.set(arr[i], [
            [i], Infinity
        ]);
    }

    let res = Infinity;

    function dfs(i, path) {
        if (i === n - 1) return res = Math.min(res, path.size);
        if (i < 0 || i > n - 1 || path.has(i)) return;

        const [idxs, min] = map.get(arr[i]);
        if (path.size >= min || path.size + 1 >= res) return;

        path.add(i);

        for (let j = 0; idxs.length > 1 && j < idxs.length; j++) {
            if (i !== idxs[j]) dfs(idxs[j], path);
        }

        dfs(i - 1, path);
        dfs(i + 1, path);

        map.get(arr[i])[1] = Math.min(map.get(arr[i])[1], path.size);
        path.delete(i);
    }

    return dfs(0, new Set()), res;
};

1、题干​

在一个 10⁶ x 10⁶ 的网格中，每个网格上方格的坐标为 (x, y) 。

现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。

每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 blocked 上。同时，不允许走出网格。

只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。

示例 1：

输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。
无法向北或者向东移动是因为方格禁止通行。
无法向南或者向西移动是因为不能走出网格。

示例 2：

输入：blocked = [], source = [0,0], target = [999999,999999]
输出：true
解释：
因为没有方格被封锁，所以一定可以到达目标方格。

提示：

• 0 <= blocked.length <= 200
• blocked[i].length == 2
• 0 <= xi, yi < 106
• source.length == target.length == 2
• 0 <= sx, sy, tx, ty < 106
• source != target
• 题目数据保证 source 和 target 不在封锁列表内

2、解题思路​

迷宫的封锁列表blocked会形成围栏，假设从起点和终点分别进行深度遍历，遍历过程中设定步数最大值steps为围栏最大面积，若2条路径行进的步数都超过最大步数或者遍历过程中起点和终点都能访问到则表示起止点连通，则表示起止点连通，反之不连通。

注意点

• 最开始认为围栏的最大面积是$(\dfrac{n}{2}) ^ 2$，是一块正方形区域。实际官解给出的是$\dfrac{n(n-1)}{2}$，是一块等腰直角三角形区域，其中n为blocked数组长度。具体实现时没看官解，限制的是$\dfrac{n^2}{2}$，实际上围栏最大面积略偏高不影响结果，因为在不被围的情况下可以走的步数肯定远超这个值。这个最大面积的推导和精确计算可以说有点复杂了，答题时被用例28教育了一番。
• 遍历过程中如果起止两个点都能访问到则表示起止点连通（用例[[0,3],[1,0],[1,1],[1,2],[1,3]] [0,0] [0,2]）
• 走过的坐标使用哈希表记录，以免重复遍历导致死循环
• JS若使用递归实现在执行用例28时会出现栈溢出（本地溢出，力扣判题程序未溢出，后面补充了递归DFS代码）

3、代码-非递归​

var isEscapePossible = function (blocked, source, target) {
    const hash = (x, y) => 1123 * x + y;
    const maxSteps = blocked.length ** 2 / 2, dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    const blockSet = blocked.reduce((a, c) => a.add(hash(c[0], c[1])), new Set());

    function move(s, t, steps, visited) {
        const stack = [s];
        while (stack.length) {
            const [x, y] = stack.pop();
            if (x < 0 || x >= 1e6 || y < 0 || y >= 1e6 || blockSet.has(hash(x, y)) || visited.has(hash(x, y))) continue;
            if (--steps <= 0 || (x === t[0] && y === t[1])) return true;
            visited.add(hash(x, y));
            for (const d of dirs) stack.push([x + d[0], y + d[1]]);
        }
        return false;
    }

    return move(source, target, maxSteps, new Set()) && move(target, source, maxSteps, new Set());
};

4、执行结果​

执行用时: 156 ms 内存消耗: 58.8 MB

5、代码-递归​

var isEscapePossible = function (blocked, source, target) {
    const hash = (x, y) => 1123 * x + y;
    const maxSteps = blocked.length ** 2 / 2, dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    const blockSet = blocked.reduce((a, c) => a.add(hash(c[0], c[1])), new Set());

    function dfs(x, y, steps, visited, t) {
        if (x < 0 || x >= 1e6 || y < 0 || y >= 1e6 || blockSet.has(hash(x, y)) || visited.has(hash(x, y))) return false;
        if (--steps <= 0 || (x === t[0] && y === t[1])) return true;
        visited.add(hash(x, y));
        return dirs.reduce((a, c) => a || dfs(x + c[0], y + c[1], steps, visited, t), false);
    }

    return dfs(...source, maxSteps, new Set(), target) && dfs(...target, maxSteps, new Set(), source);
};

6、执行结果​

执行用时: 120 ms 内存消耗: 47.8 MB

7、优化点​

• 问题：最开始哈希表保存的坐标是字符串拼接而来，但是字符串消耗空间更多、操作耗时更多，所以执行结果的时长和内存偏高
• 优化：不用字符串做key，使用质数乘法把坐标转成唯一数字，使用该唯一数字做key
• 结果：优化后两种代码执行结果用时减半（240ms 到 120ms），内存消耗也大幅减少（57.3 MB 到 47.8 MB），递归DFS代码执行结果破双百

字符串做key比较容易理解和实现且不会冲突，但消耗时间空间较多；而数字做key的好处在于消耗时间空间较少，但麻烦点在于实现时要注意避免key冲突的问题。

1、题干​

给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。

示例 1：

输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12

示例 2：

输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点

提示：

• 二叉树的节点个数的范围是  [1, 104].
• -104 <= Node.val <= 104
• root 为二叉搜索树
• -105 <= k <= 105

注意：本题与主站 653 题相同： https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/

2、解法1​

DFS遍历+哈希查找：DFS遍历所有节点node，在哈希表set中查找是否存在k - node.val，若存在则返回true否则继续遍历直至结束则返回false。

3、代码​

var findTarget = function (root, k) {
    const set = new Set();
    function dfs(node) {
        if (!node) return false;
        if (set.has(k - node.val)) return true;
        set.add(node.val);
        return dfs(node.left) || dfs(node.right);
    }
    return dfs(root);
};

4、复杂度​

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

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

5、执行结果​

6、解法2​

DFS遍历+DFS二分查找：DFS遍历所有节点node，利用BST特性进行DFS二分查找是否存在k - node.val，若存在则返回true否则继续遍历直至结束则返回false。

这里二分搜索的时间复杂度受到二叉树平衡性的影响，最坏情况下二叉树可能退化成链表，导致搜索时间复杂度为$O(n)$，总体时间复杂度为$O(n^2)$

7、代码​

var findTarget = function (root, k) {
    function find(node, num) {
        if (!node) return false;
        if (num === node.val) return true;
        return num > node.val ? find(node.right, num) : find(node.left, num);
    }

    function findSum(node, num) {
        if (!node) return false;
        return (num !== 2 * node.val && find(root, num - node.val)) || findSum(node.right, num) || findSum(node.left, num);
    }

    return findSum(root, k);
};

8、复杂度​

时间复杂度：平衡二叉搜索树的情况下为$O(nlogn)$ ，非平衡二叉搜索树的情况下超过$O(nlogn)$，最差为$O(n^2)$

空间复杂度：$O(1)$

9、执行结果​

1、题干​

如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：

• 二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
• 偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
• 奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减

给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。

示例 1：

输入：root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
输出：true
解释：每一层的节点值分别是：
0 层：[1]
1 层：[10,4]
2 层：[3,7,9]
3 层：[12,8,6,2]
由于 0 层和 2 层上的节点值都是奇数且严格递增，而 1 层和 3 层上的节点值都是偶数且严格递减，因此这是一棵奇偶树。

示例 2：

输入：root = [5,4,2,3,3,7]
输出：false
解释：每一层的节点值分别是：
0 层：[5]
1 层：[4,2]
2 层：[3,3,7]
2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。

示例 3：

输入：root = [5,9,1,3,5,7]
输出：false
解释：1 层上的节点值应为偶数。

示例 4：

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

示例 5：

输入：root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
输出：true

提示：

• 树中节点数在范围 [1, 105] 内
• 1 <= Node.val <= 106

2、解题思路​

使用广度优先遍历(BFS)或深度优先遍历(DFS)，遍历树上所有节点并判断其是否符合奇偶树的特性。

• 使用广度优先遍历(BFS)时，比较方便做到按层遍历、获取层级和兄弟节点
• 使用深度优先遍历(DFS)时，需要另外使用一个数组存储每层上一次遍历到的节点，用于判断兄弟节点的单调性

3、代码1-DFS递归实现​

执行用时：212 ms 内存消耗：82.4 MB

var isEvenOddTree = function (root) {
  const nums = [];
  function dfs(node, i) {
    if (!node) return true;
    if (i % 2 && (node.val % 2 || node.val >= nums[i])) return false;
    if (!(i % 2) && (!(node.val % 2) || node.val <= nums[i])) return false;
    nums[i] = node.val;
    return dfs(node.left, i + 1) && dfs(node.right, i + 1);
  }
  return dfs(root, 0);
};

4、代码2-BFS递归实现​

执行用时：308 ms 内存消耗：98 MB

var isEvenOddTree = function (root) {
  function bfs(nodes, i) {
    const nextArr = [];
    for (let j = 0; j < nodes.length; j++) {
      if (nodes[j].left) nextArr.push(nodes[j].left);
      if (nodes[j].right) nextArr.push(nodes[j].right);

      const m1 = i % 2, m2 = nodes[j].val % 2;
      if (m1 && (m2 || (j && nodes[j].val >= nodes[j - 1].val))) return false;
      if (!m1 && (!m2 || (j && nodes[j].val <= nodes[j - 1].val))) return false;
    }
    return !nextArr.length ? true : bfs(nextArr, i + 1);
  }
  return bfs([root], 0);
};

5、代码3-BFS非递归实现​

执行用时：276 ms 内存消耗：91.5 MB

var isEvenOddTree = function (root) {
  const queue = [[root]];
  for (let i = 0; i < queue.length; i++) {
    const nextArr = [];

    for (let j = 0; j < queue[i].length; j++) {
      if (queue[i][j].left) nextArr.push(queue[i][j].left);
      if (queue[i][j].right) nextArr.push(queue[i][j].right);

      const m1 = i % 2, m2 = queue[i][j].val % 2;
      if (m1 && (m2 || (j && queue[i][j].val >= queue[i][j - 1].val))) return false;
      if (!m1 && (!m2 || (j && queue[i][j].val <= queue[i][j - 1].val))) return false;
    }

    if (nextArr.length) queue.push(nextArr);
  }

  return true;
};

6、执行结果​

1、题干​

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
          1
         / \
        3   2
       / \   \  
      5   3   9 

示例2：

输入: root = [1,2,3]
输出: [1,3]
解释:
          1
         / \
        2   3

示例3：

输入: root = [1]
输出: [1]

示例4：

输入: root = [1,null,2]
输出: [1,2]
解释:      
           1 
            \
             2     

示例5：

输入: root = []
输出: []

提示：

• 二叉树的节点个数的范围是 [0,104]
• -231 <= Node.val <= 231 - 1

解法1：DFS递归实现​

DFS递归遍历树的每个节点，递归函数的形参中添加1个层级参数，便于计算每层节点最大值。

执行结果​

代码​

var largestValues = function (root) {
    const res = [];
    function dfs(node, level) {
        if (!node) return;
        if (res[level] === undefined || node.val > res[level]) res[level] = node.val;
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    return res;
};

解法2：BFS非递归实现​

BFS非递归遍历树的每个节点，需要借助队列实现。与常规BFS非递归实现不同，此处队列是一个矩阵，队列中的元素是每层节点的集合。

执行结果​

代码​

var largestValues = function (root) {
    const queue = root ? [[root]] : [], res = [];
    for (const curNodes of queue) {
        let max = -Infinity, nodes = [];
        for (const node of curNodes) {
            if (node.val > max) max = node.val;
            if (node.left) nodes.push(node.left);
            if (node.right) nodes.push(node.right);
        }
        if (nodes.length) queue.push(nodes);
        res.push(max);
    }
    return res;
};

由于非递归实现需要额外借助数组实现，且存在大量Array.push()等耗时操作，所以时间和空间上会消耗得更多

1、题干​

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

• 二叉树的节点个数的范围是 [1,104]
• -231 <= Node.val <= 231 - 1 

执行结果​

解题思路​

总体思路：使用DFS递归遍历树的所有节点，当第一次遍历到层级大于所有已遍历节点的节点时，该节点就是当前层级的最左子节点；随着遍历层级递增，最终能找到最底层的最左子节点。

• 使用DFS递归遍历树的所有节点
• 记录当前节点的层级level与已遍历节点的最大层级maxLevel
• 每当level超过maxLevel时，将当前节点赋值给res，另外更新maxLevel
• 遍历完成后，res就是要找的节点，返回该节点的值即可

代码​

var findBottomLeftValue = function (root) {
    let res, maxLevel = 0;
    function dfs(node, level) {
        if (!node) return;
        if (level > maxLevel) res = node, maxLevel = level;
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 1);
    return res && res.val;
};

1、题干​

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

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

• 二叉树的节点个数的范围是 [0,100]
• -100 <= Node.val <= 100 

执行结果​

解题思路​

总体思路：使用DFS递归遍历树的所有节点，创建结果数组res，将当前节点的层级当做res的下标、val当做res的值，以此更新res，右边节点的值会不断覆盖左边节点，得到的数组就是从右侧所能看到的节点值。

代码​

var rightSideView = function (root) {
    const res = [];
    function dfs(node, level) {
        if (!node) return;
        res[level] = node.val;
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    return res;
};

1、题干​

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
          1
         / \
        3   2
       / \   \  
      5   3   9 

示例2：

输入: root = [1,2,3]
输出: [1,3]
解释:
          1
         / \
        2   3

示例3：

输入: root = [1]
输出: [1]

示例4：

输入: root = [1,null,2]
输出: [1,2]
解释:      
           1 
            \
             2     

示例5：

输入: root = []
输出: []

提示：

• 二叉树的节点个数的范围是 [0,104]
• -231 <= Node.val <= 231 - 1

解法1：DFS递归实现​

DFS递归遍历树的每个节点，递归函数的形参中添加1个层级参数，便于计算每层节点最大值。

执行结果​

代码​

var largestValues = function (root) {
    const res = [];
    function dfs(node, level) {
        if (!node) return;
        if (res[level] === undefined || node.val > res[level]) res[level] = node.val;
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    return res;
};

解法2：BFS非递归实现​

BFS非递归遍历树的每个节点，需要借助队列实现。与常规BFS非递归实现不同，此处队列是一个矩阵，队列中的元素是每层节点的集合。

执行结果​

代码​

var largestValues = function (root) {
    const queue = root ? [[root]] : [], res = [];
    for (const curNodes of queue) {
        let max = -Infinity, nodes = [];
        for (const node of curNodes) {
            if (node.val > max) max = node.val;
            if (node.left) nodes.push(node.left);
            if (node.right) nodes.push(node.right);
        }
        if (nodes.length) queue.push(nodes);
        res.push(max);
    }
    return res;
};

由于非递归实现需要额外借助数组实现，且存在大量Array.push()等耗时操作，所以时间和空间上会消耗得更多