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

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

给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
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!
提示
  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。

方法一 递归法

思路
使用树的先序遍历(递归方式)。这里需要解决两种情形,第一,同一父节点的左右节点的连接,如图中的 23 节点;第二,相近但非同一直系父节点的节点相连,如图中的 56 节点。
详解
  1. 1.
    第一步,同一父节点的左右节点的连接:先将同一父节点的左节点的 next 指向右节点,以图例中的节点 1 为例,其左节点 2next 指向右节点 3
  2. 2.
    第二步,相近但非同一直系父节点的节点相连:考虑到不同直系父节点的同一层节点也需要相连,以图例中的节点 56 为例,5next 指向 6。我们可以通过 5 的父节点 2next 节点找到 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(1)O(1)
    由于题目提示中声明,递归程序占用的栈空间不算做额外的空间复杂度,因此为
    O(1)O(1)

方法二 层序遍历法(队列方式)

思路
使用层序遍历的方法,每一层按从左到右进行遍历,把遍历出来的节点依次连接起来,但在连接的时候需要注意,每层的最后一个节点的 next 需要置为 null,而不是和前一个节点相连。
详解
  1. 1.
    第一步,进行二叉树的层序遍历,每一层按从左到右进行遍历,把遍历出来的节点依次连接起来。 补充说明:如何进行二叉树的层序遍历?核心思想是使用队列先进先出的特性。 以上述示例图中的二叉树为例。首先初始化,将根节点 1 推入队列,然后,首位(即节点 1)出队列,并将其左子节点 2 和右子节点 3 推入队列,然后,首位(即节点 2)出队列,并将其左子节点 4 和右子节点 5 推入队列,接下去,节点 3 出队列,节点 4 5 入队列,依次类推,直到队列为空,二叉树遍历结束。
  2. 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)
    由于解法中使用到队列,且在访问最下面一层叶子节点时,空间占用达到最大,即存储了
    (n+1)/2(n+1)/2
    个节点,因此为
    O(n)O(n)

方法三 层序遍历法(指针方式)

思路
使用 2 个指针 startcurrent 来进行层序遍历。其中 start 用于标记每一层的第一个节点,current 用来遍历该层的其他节点。
详解
  1. 1.
    第一步,定义一个 start 指针,用于标记每一层的第一个节点,start 指针的初始化值为 root 节点,只需要 start = start.left,就能获取到每一层的第一个节点。
  2. 2.
    第二步,定义一个 current 指针,用来遍历该层的其他节点。然后,将同一父节点的左右节点的连接,即current.left.next = current.right,如图中的 23 节点;将相近但非同一直系父节点的节点相连,即current.right.next = current.next.left,如图中的 56 节点。
代码
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)
    本解法中,外层循环总共执行 k 次(其中 k 为树的最大深度),内层循环根据所在的层次不同而不同,第一层1次,第二层 2 次,第 k 层
    2k12^{k-1}
    次,而
    1+2+...(2k1)=n1+2+...(2^{k-1})=n
    ,即所有节点数之和,因此时间复杂度为
    O(n)O(n)
  • 空间复杂度:
    O(1)O(1)
    由于解法中只申请了 2 个变量,空间复杂度与树的节点个数 n 无关,因此为
    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. 1.
    定义岛屿数量计数变量 landNum
  2. 2.
    对二维数组 grid 进行两层遍历
  3. 3.
    遍历过程中,遇到为 1 的陆地则将 landNum 自增 1,然后进入传播函数,并传入当前的坐标 ij
  4. 4.
    根据传入的坐标,判断是否超出 grid 边界,并判断是否为 0
  5. 5.
    若为超出边界,或为 0,则停止传播
  6. 6.
    若为边界内的 1,则将该位置变为 0,并对此节点的上下左右节点继续递归传播,以此实现深度优先遍历
  7. 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)
    n 为传入的二维网络的节点个数
  • 空间复杂度:
    O(n)O(n)
    最坏情况下为
    O(n)O(n)
    ,此时整个网格均为陆地

方法二 广度优先遍历

思路
遍历二维数组,当节点为陆地(1)时,启动广度优先遍历搜索,将节点坐标放入队列中,并将计数器加 1。在搜索过程中,遇到陆地(1)节点便标记为海水(0)节点,迭代搜索队列中的每个结点,直到队列为空。
详解
  1. 1.
    定义岛屿数量计数变量 landNum
  2. 2.
    对二维数组 grid 进行两层遍历
  3. 3.
    遍历过程中,遇到为 1 的陆地则将 landNum 自增 1,然后进入传播函数,并传入当前的坐标 ij
  4. 4.
    根据传入的坐标,构造成 queue 队列数组
  5. 5.
    循环判断 queue 的数组长度
  6. 6.
    若数组中存在坐标,则将末尾坐标从 queuepop 取出
  7. 7.
    判断取出的坐标是否为边界内的 1,若是,则将此坐标设置为 0,并将此坐标的上下左右坐标存入 queue 数组中,以此完成广度优先遍历
  8. 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)
    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. 1.
    定义两个数组,一个接收奇数层元素,另一个接收偶数层元素。
  2. 2.
    奇数层遍历完成之后,将下一层元素由左向右插入偶数层数组。
  3. 3.
    先进后出原则,偶数列遍历时,取值顺序就变成了由右向左取值。
  4. 4.
    偶数层遍历完成之后,将下一层元素由右向左插入奇数层数组。
  5. 5.
    先进后出原则,奇数列遍历时,取值顺序就变成了由左向右取值。
  6. 6.
    循环往复,形成锯齿形层次遍历
详解
  1. 1.
    定义结果数组
  2. 2.
    定义两个数组模拟栈(l2r、r2l),一个由左向右,一个由右向左
  3. 3.
    将要处理的数据 push 到 l2r,进行循环
  4. 4.
    每层循环定义一个 临时数组,接收当前层的结果,最后需要 push 到结果数组。
  5. 5.
    第一层 l2r 就一个根数据,直接就将当前值 push 到 临时数组。为了方便交替遍历,将 l2r 的下一层数据 由左向右 push 到 r2l
  6. 6.
    第二层 r2l 的数据是由左向右,先进后出,所以我们循环取值是 由右向左,将当前结果 push 到 临时数组,然后将 r2l 的下一层数据 由右向左 push 到 l2r
  7. 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)

方法二 递归

思路
采用递归,一层层遍历。每一层创建一个数组,奇数层元素从左向右插入数组,偶数层元素从右向左插入数组。
& 与操作符 判断奇偶
详解
  1. 1.
    先在最层城定义返回结果数组
  2. 2.
    然后看递归方法
    1. 1.
      定义两个参数。第一个 i 层数减一,对应返回结果数组的索引值;第二个 current ,当前处理对象;
    2. 2.
      首先判断结果数组当前索引的是否为第一次创建,不是创建新数组
    3. 3.
      索引为奇数,对应树形结构偶数行,从右向左插入
    4. 4.
      索引为偶数,对应树形结构奇数行,从左向右插入
    5. 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)