101道算法JavaScript描述【二叉树】7

填充每个节点的下一个右侧节点指针、岛屿数量和二叉树的锯齿形层次遍历

填充每个节点的下一个右侧节点指针

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

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

填充它的每个

next

指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将

next

指针设置为

NULL

。 初始状态下，所有

next

指针都被设置为

NULL

。

示例

输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点

提示

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

方法一 递归法

思路

使用树的先序遍历（递归方式）。这里需要解决两种情形，第一，同一父节点的左右节点的连接，如图中的

2

、

3

节点；第二，相近但非同一直系父节点的节点相连，如图中的

5

、

6

节点。

详解

1. 第一步，同一父节点的左右节点的连接：先将同一父节点的左节点的 next 指向右节点，以图例中的节点 1 为例，其左节点 2 的 next 指向右节点 3。
2. 第二步，相近但非同一直系父节点的节点相连：考虑到不同直系父节点的同一层节点也需要相连，以图例中的节点 5、6 为例，5 的 next 指向 6。我们可以通过 5 的父节点 2 的 next 节点找到 3，再通过节点 3，找到节点 6，即访问节点 3 的左节点。以此类推，无论下面还有多少层，都可以通过这种方法，连接相近但不是同一直系父节点的两个子节点。

代码

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 *//**
 * @param {Node} root
 * @return {Node}
 */constconnect=(root)=>{// 递归出口if(root ===null){return root;}// 同一父节点的左右节点相连，如图中 2、3 节点相连if(!!root.left &&!!root.right){
    root.left.next = root.right;}// 相近但非同一直系父节点的节点相连，如图中 5、6 节点相连if(!!root.right && root.next && root.next.left){
    root.right.next = root.next.left;}connect(root.left);connect(root.right);return root;};

复杂度分析

• 时间复杂度：O(n)O(n)上述解法中，树的每个节点只访问了一次，时间复杂度跟树的节点个数线性相关，因此为 O(n)O(n)。
• 空间复杂度：O(1)O(1)由于题目提示中声明，递归程序占用的栈空间不算做额外的空间复杂度，因此为 O(1)O(1)。

方法二 层序遍历法（队列方式）

思路

使用层序遍历的方法，每一层按从左到右进行遍历，把遍历出来的节点依次连接起来，但在连接的时候需要注意，每层的最后一个节点的

next

需要置为

null

，而不是和前一个节点相连。

详解

1. 第一步，进行二叉树的层序遍历，每一层按从左到右进行遍历，把遍历出来的节点依次连接起来。 补充说明：如何进行二叉树的层序遍历？核心思想是使用队列先进先出的特性。 以上述示例图中的二叉树为例。首先初始化，将根节点 1 推入队列，然后，首位（即节点 1）出队列，并将其左子节点 2 和右子节点 3 推入队列，然后，首位（即节点 2）出队列，并将其左子节点 4 和右子节点 5 推入队列，接下去，节点 3 出队列，节点 4``````5 入队列，依次类推，直到队列为空，二叉树遍历结束。
2. 第二步，在连接的时候，判断当前遍历到的节点是否为该层的最右节点。具体判断方法如下：因为层序遍历过程中，队列的 size 即为当前层节点的总个数，使用 for 循环进行当前层的遍历，循环执行的最后一次就是该层最后一个节点。

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 *//**
 * @param {Node} root
 * @return {Node}
 */constconnect=(root)=>{const arr =[];if(root ===null){return root;}
  arr.push(root);while(arr.length){// size 为每一层节点的总个数。 prevNode 记录前一个节点。const size = arr.length;let prevNode;let node;// 遍历每一层的节点for(let i =0; i < size; i +=1){
      node = arr.shift();// 出队列// 每一层最后一个节点的 next 需要置为 null// 因此，当前节点不是当前层的最后一个节点的话，将当前节点与前一节点连接if(prevNode && i < size){
        prevNode.next = node;}if(node.left){
        arr.push(node.left);// 左节点入队列}if(node.right){
        arr.push(node.right);// 右节点入队列}
      prevNode = node;}}return root;};

复杂度分析

• 时间复杂度：O(n)O(n)上述解法中，树的每个节点只访问了一次，时间复杂度跟树的节点个数线性相关，因此为 O(n)O(n)。
• 空间复杂度：O(n)O(n)由于解法中使用到队列，且在访问最下面一层叶子节点时，空间占用达到最大，即存储了 (n+1)/2(n+1)/2 个节点，因此为 O(n)O(n)。

方法三 层序遍历法（指针方式）

思路

使用 2 个指针

start

和

current

来进行层序遍历。其中

start

用于标记每一层的第一个节点，

current

用来遍历该层的其他节点。

详解

1. 第一步，定义一个 start 指针，用于标记每一层的第一个节点，start 指针的初始化值为 root 节点，只需要 start = start.left，就能获取到每一层的第一个节点。
2. 第二步，定义一个 current 指针，用来遍历该层的其他节点。然后，将同一父节点的左右节点的连接，即current.left.next = current.right，如图中的 2、3 节点；将相近但非同一直系父节点的节点相连，即current.right.next = current.next.left，如图中的 5、6 节点。

代码

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 *//**
 * @param {Node} root
 * @return {Node}
 */constconnect=(root)=>{if(root ===null){return root;}let start = root;let current =null;// start 为每一层的第一个节点while(start.left){// 每一层节点的遍历
    current = start;while(current){// 同一父节点的左右节点相连，如图中 2、3 节点相连
      current.left.next = current.right;// 相近但非同一直系父节点的节点相连，如图中 5、6 节点相连if(current.next){
        current.right.next = current.next.left;}
      current = current.next;}
    start = start.left;}return root;};

复杂度分析

• 时间复杂度：O(n)O(n)本解法中，外层循环总共执行 k 次（其中 k 为树的最大深度），内层循环根据所在的层次不同而不同，第一层1次，第二层 2 次，第 k 层 2^{k-1}2k−1 次，而 1+2+…(2^{k-1})=n1+2+…(2k−1)=n，即所有节点数之和，因此时间复杂度为 O(n)O(n)。
• 空间复杂度：O(1)O(1)由于解法中只申请了 2 个变量，空间复杂度与树的节点个数 n 无关，因此为 O(1)O(1)。

岛屿数量

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1：

输入:
11110
11010
11000
00000

输出: 1

示例 2：

输入:
11000
11000
00100
00011

输出: 3

方法一 深度优先遍历

思路

遍历二维数组，当节点为陆地(1)时，对当前节点的上下左右四个方向启动深度优先遍历搜索，并将计数器加 1。同时在搜索过程中，遇到海水(0)节点便停止，遇到陆地(1)节点便标记为海水(0)节点。

详解

1. 定义岛屿数量计数变量 landNum
2. 对二维数组 grid 进行两层遍历
3. 遍历过程中，遇到为 1 的陆地则将 landNum 自增 1，然后进入传播函数，并传入当前的坐标 i、j
4. 根据传入的坐标，判断是否超出 grid 边界，并判断是否为 0
5. 若为超出边界，或为 0，则停止传播
6. 若为边界内的 1，则将该位置变为 0，并对此节点的上下左右节点继续递归传播，以此实现深度优先遍历
7. 传播结束后，便可根据 landNum 获得岛屿数量

代码

/**
 * @param {character[][]} grid
 * @return {number}
 */varnumIslands=function(grid){let landNum =0for(let i =0; i < grid.length; i++){const len = grid[i].length;for(let j =0; j < len; j++){const target = grid[i][j]if(target ==='1'){spread(grid, i, j)
                landNum++}}}return landNum;};/**
 * @param {character[][]} grid
 * @param {number} i
 * @param {number} j
 */functionspread(grid, i, j){if(i <0|| j <0|| i >= grid.length || j >= grid[i].length || grid[i][j]!=='1'){return}

  grid[i][j]='0'spread(grid, i, j +1);spread(grid, i, j -1);spread(grid, i +1, j);spread(grid, i -1, j);}

复杂度分析

• 时间复杂度：O(n)O(n)n 为传入的二维网络的节点个数
• 空间复杂度：O(n)O(n)最坏情况下为 O(n)O(n)，此时整个网格均为陆地

方法二 广度优先遍历

思路

遍历二维数组，当节点为陆地(1)时，启动广度优先遍历搜索，将节点坐标放入队列中，并将计数器加 1。在搜索过程中，遇到陆地(1)节点便标记为海水(0)节点，迭代搜索队列中的每个结点，直到队列为空。

详解

1. 定义岛屿数量计数变量 landNum
2. 对二维数组 grid 进行两层遍历
3. 遍历过程中，遇到为 1 的陆地则将 landNum 自增 1，然后进入传播函数，并传入当前的坐标 i、j
4. 根据传入的坐标，构造成 queue 队列数组
5. 循环判断 queue 的数组长度
6. 若数组中存在坐标，则将末尾坐标从 queue 中 pop 取出
7. 判断取出的坐标是否为边界内的 1，若是，则将此坐标设置为 0，并将此坐标的上下左右坐标存入 queue 数组中，以此完成广度优先遍历
8. 遍历结束后，便可根据 landNum 获得岛屿数量

代码

/**
 * @param {character[][]} grid
 * @return {number}
 */varnumIslands=function(grid){let landNum =0for(let i =0; i < grid.length; i++){const len = grid[i].length;for(let j =0; j < len; j++){const target = grid[i][j]if(target ==='1'){spread(grid, i, j)
                landNum++}}}return landNum;};/**
 * @param {character[][]} grid
 * @param {number} i
 * @param {number} j
 */functionspread(grid, i, j){const queue =[[i, j]]while(!!queue.length){const[i, j]= queue.pop()if(grid.length > i 
            && i >=0&& grid[0].length > j
            && j >=0&& grid[i][j]==='1'){

            grid[i][j]='0'
            queue.push([i -1, j])
            queue.push([i +1, j])
            queue.push([i, j +1])
            queue.push([i, j -1])}}}

复杂度分析

• 时间复杂度：O(n)O(n)n 为传入的二维网络的节点个数
• 空间复杂度：O(n)O(n)最坏情况下为 O(n)O(n)，此时整个网格均为陆地

二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例

给定二叉树 [3, 9, 20, null, null, 15, 7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

方法一 双栈法

思路

栈：是一种数据结构，先进后出原则。

双栈法：

1. 定义两个数组，一个接收奇数层元素，另一个接收偶数层元素。
2. 奇数层遍历完成之后，将下一层元素由左向右插入偶数层数组。
3. 先进后出原则，偶数列遍历时，取值顺序就变成了由右向左取值。
4. 偶数层遍历完成之后，将下一层元素由右向左插入奇数层数组。
5. 先进后出原则，奇数列遍历时，取值顺序就变成了由左向右取值。
6. 循环往复，形成锯齿形层次遍历

详解

1. 定义结果数组
2. 定义两个数组模拟栈(l2r、r2l)，一个由左向右，一个由右向左
3. 将要处理的数据 push 到 l2r，进行循环
4. 每层循环定义一个 临时数组，接收当前层的结果，最后需要 push 到结果数组。
5. 第一层 l2r 就一个根数据，直接就将当前值 push 到 临时数组。为了方便交替遍历，将 l2r 的下一层数据 由左向右 push 到 r2l
6. 第二层 r2l 的数据是由左向右，先进后出，所以我们循环取值是 由右向左，将当前结果 push 到 临时数组，然后将 r2l 的下一层数据 由右向左 push 到 l2r
7. 循环往复

代码

constzigzagLevelOrder=function(root){if(!root)return[];const res =[];const l2r =[];const r2l =[];
  l2r.push(root);while(l2r.length || r2l.length){const temp =[];if(l2r.length){while(l2r.length){const cur = l2r.pop();
        temp.push(cur.val);if(cur.left) r2l.push(cur.left);if(cur.right) r2l.push(cur.right);}}elseif(r2l.length){while(r2l.length){const cur = r2l.pop();
        temp.push(cur.val);if(cur.right) l2r.push(cur.right);if(cur.left) l2r.push(cur.left);}}
    res.push(temp);}return res;};

复杂度分析

• 时间复杂度：O(n)O(n)每个节点都要进栈和出栈，所以时间复杂度为 O(n)O(n)
• 空间复杂度：O(n)O(n)双栈每个节点的值也只记录一次，所以空间复杂度为 O(n)O(n)

方法二 递归

思路

采用递归，一层层遍历。每一层创建一个数组，奇数层元素从左向右插入数组，偶数层元素从右向左插入数组。

& 与操作符 判断奇偶

详解

1. 先在最层城定义返回结果数组
2. 然后看递归方法 1. 定义两个参数。第一个 i 层数减一，对应返回结果数组的索引值；第二个 current ，当前处理对象；2. 首先判断结果数组当前索引的是否为第一次创建，不是创建新数组3. 索引为奇数，对应树形结构偶数行，从右向左插入4. 索引为偶数，对应树形结构奇数行，从左向右插入5. 然后不断递归

代码

constzigzagLevelOrder=function(root){const res =[];dfs(0, root);return res;functiondfs(i, current){if(!current)return;// 首次进入该层递归，现在结果创建新数组用来接收结果。if(!Array.isArray(res[i])) res[i]=[];// 判断当前层数索引奇偶// 奇数从前插入数组，偶数从后插入数组if(i &1) res[i].unshift(current.val);else res[i].push(current.val);// 左侧子二叉树进入递归dfs(i +1, current.left);// 右侧子二叉树进入递归dfs(i +1, current.right);}};

复杂度分析

• 时间复杂度：O(n)O(n)因为每个节点恰好会被运算一次
• 空间复杂度：O(n)O(n)系统栈需要记住每个节点的值，所以空间复杂度为 O(n)O(n)