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

搜索文档…
填充每个节点的下一个右侧节点指针
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
1
struct Node {
2
  int val;
3
  Node *left;
4
  Node *right;
5
  Node *next;
6
}
Copied!
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next 指针都被设置为 NULL。
示例
Could not load image
1
输入：{"$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}
2
​
3
输出：{"$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}
4
​
5
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
Copied!
提示
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
方法一 递归法
思路
使用树的先序遍历（递归方式）。这里需要解决两种情形，第一，同一父节点的左右节点的连接，如图中的 2、3 节点；第二，相近但非同一直系父节点的节点相连，如图中的 5、6 节点。
详解
1.第一步，同一父节点的左右节点的连接：先将同一父节点的左节点的 next 指向右节点，以图例中的节点 1 为例，其左节点 2 的 next 指向右节点 3。
2.第二步，相近但非同一直系父节点的节点相连：考虑到不同直系父节点的同一层节点也需要相连，以图例中的节点 5、6 为例，5 的 next 指向 6。我们可以通过 5 的父节点 2 的 next 节点找到 3，再通过节点 3，找到节点 6，即访问节点 3 的左节点。以此类推，无论下面还有多少层，都可以通过这种方法，连接相近但不是同一直系父节点的两个子节点。
代码
1
/**
2
 * // Definition for a Node.
3
 * function Node(val, left, right, next) {
4
 *    this.val = val === undefined ? null : val;
5
 *    this.left = left === undefined ? null : left;
6
 *    this.right = right === undefined ? null : right;
7
 *    this.next = next === undefined ? null : next;
8
 * };
9
 */
10
/**
11
 * @param {Node} root
12
 * @return {Node}
13
 */
14
const connect = (root) => {
15
  // 递归出口
16
  if (root === null) {
17
    return root;
18
  }
19
  // 同一父节点的左右节点相连，如图中 2、3 节点相连
20
  if (!!root.left && !!root.right) {
21
    root.left.next = root.right;
22
  }
23
  // 相近但非同一直系父节点的节点相连，如图中 5、6 节点相连
24
  if (!!root.right && root.next && root.next.left) {
25
    root.right.next = root.next.left;
26
  }
27
  connect(root.left);
28
  connect(root.right);
29
  return root;
30
};
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
上述解法中，树的每个节点只访问了一次，时间复杂度跟树的节点个数线性相关，因此为 O(n)O(n)O(n)
。
空间复杂度：O(1)O(1)O(1)
​
由于题目提示中声明，递归程序占用的栈空间不算做额外的空间复杂度，因此为 O(1)O(1)O(1)
。
方法二 层序遍历法（队列方式）
思路
使用层序遍历的方法，每一层按从左到右进行遍历，把遍历出来的节点依次连接起来，但在连接的时候需要注意，每层的最后一个节点的 next 需要置为 null，而不是和前一个节点相连。
详解
1.第一步，进行二叉树的层序遍历，每一层按从左到右进行遍历，把遍历出来的节点依次连接起来。 补充说明：如何进行二叉树的层序遍历？核心思想是使用队列先进先出的特性。 以上述示例图中的二叉树为例。首先初始化，将根节点 1 推入队列，然后，首位（即节点 1）出队列，并将其左子节点 2 和右子节点 3 推入队列，然后，首位（即节点 2）出队列，并将其左子节点 4 和右子节点 5 推入队列，接下去，节点 3 出队列，节点 4 5 入队列，依次类推，直到队列为空，二叉树遍历结束。
2.第二步，在连接的时候，判断当前遍历到的节点是否为该层的最右节点。具体判断方法如下：因为层序遍历过程中，队列的 size 即为当前层节点的总个数，使用 for 循环进行当前层的遍历，循环执行的最后一次就是该层最后一个节点。
1
/**
2
 * // Definition for a Node.
3
 * function Node(val, left, right, next) {
4
 *    this.val = val === undefined ? null : val;
5
 *    this.left = left === undefined ? null : left;
6
 *    this.right = right === undefined ? null : right;
7
 *    this.next = next === undefined ? null : next;
8
 * };
9
 */
10
/**
11
 * @param {Node} root
12
 * @return {Node}
13
 */
14
const connect = (root) => {
15
  const arr = [];
16
  if (root === null) {
17
    return root;
18
  }
19
  arr.push(root);
20
  while (arr.length) {
21
    // size 为每一层节点的总个数。 prevNode 记录前一个节点。
22
    const size = arr.length;
23
    let prevNode;
24
    let node;
25
    // 遍历每一层的节点
26
    for (let i = 0; i < size; i += 1) {
27
      node = arr.shift(); // 出队列
28
      // 每一层最后一个节点的 next 需要置为 null
29
      // 因此，当前节点不是当前层的最后一个节点的话，将当前节点与前一节点连接
30
      if (prevNode && i < size) {
31
        prevNode.next = node;
32
      }
33
      if (node.left) {
34
        arr.push(node.left); // 左节点入队列
35
      }
36
      if (node.right) {
37
        arr.push(node.right); // 右节点入队列
38
      }
39
      prevNode = node;
40
    }
41
  }
42
  return root;
43
};
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
上述解法中，树的每个节点只访问了一次，时间复杂度跟树的节点个数线性相关，因此为 O(n)O(n)O(n)
。
空间复杂度：O(n)O(n)O(n)
​
由于解法中使用到队列，且在访问最下面一层叶子节点时，空间占用达到最大，即存储了 (n+1)/2(n+1)/2(n+1)/2
 个节点，因此为 O(n)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 节点。
代码
1
/**
2
 * // Definition for a Node.
3
 * function Node(val, left, right, next) {
4
 *    this.val = val === undefined ? null : val;
5
 *    this.left = left === undefined ? null : left;
6
 *    this.right = right === undefined ? null : right;
7
 *    this.next = next === undefined ? null : next;
8
 * };
9
 */
10
/**
11
 * @param {Node} root
12
 * @return {Node}
13
 */
14
const connect = (root) => {
15
  if (root === null) {
16
    return root;
17
  }
18
  let start = root;
19
  let current = null;
20
  // start 为每一层的第一个节点
21
  while (start.left) {
22
    // 每一层节点的遍历
23
    current = start;
24
    while (current) {
25
      // 同一父节点的左右节点相连，如图中 2、3 节点相连
26
      current.left.next = current.right;
27
      // 相近但非同一直系父节点的节点相连，如图中 5、6 节点相连
28
      if (current.next) {
29
        current.right.next = current.next.left;
30
      }
31
      current = current.next;
32
    }
33
    start = start.left;
34
  }
35
  return root;
36
};
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
本解法中，外层循环总共执行 k 次（其中 k 为树的最大深度），内层循环根据所在的层次不同而不同，第一层1次，第二层 2 次，第 k 层 2k−12^{k-1}2k−1
 次，而 1+2+...(2k−1)=n1+2+...(2^{k-1})=n1+2+...(2k−1)=n
，即所有节点数之和，因此时间复杂度为 O(n)O(n)O(n)
。
空间复杂度：O(1)O(1)O(1)
​
由于解法中只申请了 2 个变量，空间复杂度与树的节点个数 n 无关，因此为 O(1)O(1)O(1)
。
岛屿数量
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1：
1
输入:
2
11110
3
11010
4
11000
5
00000
6
​
7
输出: 1
Copied!
示例 2：
1
输入:
2
11000
3
11000
4
00100
5
00011
6
​
7
输出: 3
Copied!
方法一 深度优先遍历
思路
遍历二维数组，当节点为陆地(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 获得岛屿数量
代码
1
/**
2
 * @param {character[][]} grid
3
 * @return {number}
4
 */
5
var numIslands = function(grid) {
6
  let landNum = 0
7
​
8
  for(let i = 0; i < grid.length; i++) {
9
        const len = grid[i].length;
10
        for(let j = 0; j < len; j++) {
11
            const target = grid[i][j]
12
            if (target === '1') {
13
                spread(grid, i, j)
14
                landNum++
15
            }
16
        }
17
  }
18
  return landNum;
19
};
20
​
21
/**
22
 * @param {character[][]} grid
23
 * @param {number} i
24
 * @param {number} j
25
 */
26
function spread(grid, i, j) {
27
  if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] !== '1') {
28
        return
29
  }
30
​
31
  grid[i][j] = '0'
32
  spread(grid, i, j + 1);
33
  spread(grid, i, j - 1);
34
  spread(grid, i + 1, j);
35
  spread(grid, i - 1, j);
36
}
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
n 为传入的二维网络的节点个数
空间复杂度：O(n)O(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 获得岛屿数量
代码
1
/**
2
 * @param {character[][]} grid
3
 * @return {number}
4
 */
5
var numIslands = function(grid) {
6
    let landNum = 0
7
​
8
  for(let i = 0; i < grid.length; i++) {
9
        const len = grid[i].length;
10
        for(let j = 0; j < len; j++) {
11
            const target = grid[i][j]
12
            if (target === '1') {
13
                spread(grid, i, j)
14
                landNum++
15
            }
16
        }
17
    }
18
​
19
  return landNum;
20
};
21
​
22
​
23
/**
24
 * @param {character[][]} grid
25
 * @param {number} i
26
 * @param {number} j
27
 */
28
function spread(grid, i, j) {
29
  const queue = [[i, j]]
30
​
31
  while (!!queue.length) {
32
        const [i, j] = queue.pop()
33
        if (grid.length > i 
34
            && i >= 0
35
            && grid[0].length > j
36
            && j >= 0
37
            && grid[i][j] === '1') {
38
​
39
            grid[i][j] = '0'
40
            queue.push([i - 1, j])
41
            queue.push([i + 1, j])
42
            queue.push([i, j + 1])
43
            queue.push([i, j - 1])
44
        }
45
    }
46
}
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
n 为传入的二维网络的节点个数
空间复杂度：O(n)O(n)O(n)
​
最坏情况下为 O(n)O(n)O(n)
，此时整个网格均为陆地
二叉树的锯齿形层次遍历
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例
给定二叉树 [3, 9, 20, null, null, 15, 7],
1
    3
2
   / \
3
  9  20
4
    /  \
5
   15   7
Copied!
返回锯齿形层次遍历如下：
1
[
2
  [3],
3
  [20,9],
4
  [15,7]
5
]
Copied!
方法一 双栈法
思路
栈：是一种数据结构，先进后出原则。
双栈法：
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.循环往复
代码
1
const zigzagLevelOrder = function (root) {
2
  if (!root) return [];
3
  const res = [];
4
  const l2r = [];
5
  const r2l = [];
6
  l2r.push(root);
7
  while (l2r.length || r2l.length) {
8
    const temp = [];
9
    if (l2r.length) {
10
      while (l2r.length) {
11
        const cur = l2r.pop();
12
        temp.push(cur.val);
13
        if (cur.left) r2l.push(cur.left);
14
        if (cur.right) r2l.push(cur.right);
15
      }
16
    } else if (r2l.length) {
17
      while (r2l.length) {
18
        const cur = r2l.pop();
19
        temp.push(cur.val);
20
        if (cur.right) l2r.push(cur.right);
21
        if (cur.left) l2r.push(cur.left);
22
      }
23
    }
24
    res.push(temp);
25
  }
26
  return res;
27
};
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
每个节点都要进栈和出栈，所以时间复杂度为 O(n)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.然后不断递归
代码
1
const zigzagLevelOrder = function (root) {
2
  const res = [];
3
  dfs(0, root);
4
  return res;
5
  function dfs (i, current) {
6
    if (!current) return;
7
    // 首次进入该层递归，现在结果创建新数组用来接收结果。
8
    if (!Array.isArray(res[i])) res[i] = [];
9
    // 判断当前层数索引奇偶
10
    // 奇数从前插入数组，偶数从后插入数组
11
    if (i & 1) res[i].unshift(current.val);
12
    else res[i].push(current.val);
13
    // 左侧子二叉树进入递归
14
    dfs(i + 1, current.left);
15
    // 右侧子二叉树进入递归
16
    dfs(i + 1, current.right);
17
  }
18
};
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
因为每个节点恰好会被运算一次
空间复杂度：O(n)O(n)O(n)
​
系统栈需要记住每个节点的值，所以空间复杂度为 O(n)O(n)O(n)
​