LeetCode题目总结-二叉树的遍历

遍历的含义就是把树的所有节点(Node)按照某种顺序访问一遍。包括前序,中序,后序,层序4种遍历方法。

  1. 以图的深度优先搜索为原型的遍历

在这种类型中,递归的实现方式是非常简单的,只需要递归左右结点,直到结点为空作为结束条件就可以,哪种序就取决于你访问结点的时间。

不过一般这不能满足面试官的要求,可能会接着问能不能用非递归实现一下,这个说起来比较简单,其实就是用一个栈手动模拟递归的过程。

有时候非递归还是不能满足面试官,还会问一问,上面的做法时间和空间复杂度是多少。我们知道,正常遍历时间复杂度是O(n),而空间复杂度是则是递归栈(或者自己维护的栈)的大小,也就是O(logn)。他会问能不能够在常量空间内解决树的遍历问题呢?确实还真可以,这里就要介绍一下Morris遍历。

Morris遍历方法用了线索二叉树,这个方法不需要为每个节点额外分配指针指向其前驱和后继结点,而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了。这样就节省了需要用栈来记录前驱或者后继结点的额外空间,所以可以达到O(1)的空间复杂度。不过这种方法有一个问题就是会暂时性的改动树的结构,这在程序设计中并不是很好的习惯,这些在面试中都可以和面试官讨论,一般来说问到这里不会需要进行Morris遍历方法的代码实现了,只需要知道这种方法和他的主要优劣势就可以了。

  1. 以图的广度优先搜索为原型的遍历,在树中称为层序遍历,LeetCode中有三种:自顶向下层序、自底向上层序、锯齿层序遍历。

自顶向下层序遍历其实比较简单,代码基本就是图的广度优先搜索,思路就是维护一个队列存储上一层的结点,逐层访问。而自底向上层序层序遍历则要从最后一层倒序访问上来,这个我没有想到太好的方法,现在的实现就是把自顶向下层序遍历得到的层放入数据结构然后reverse过来。至于锯齿层序遍历因为每一层访问顺序有所改变,而且是每次都反转顺序,这让我们想到这个数据结构,所以这里不用队列而改用栈来保存,就可以满足每层反转访问顺序的要求了。

层次遍历相关的题目:

以图的深度优先搜索为原型的遍历

144-二叉树的前序遍历

题目描述

给定一个二叉树,返回它的 前序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]  
1
\
2
/
3

输出: [1,2,3]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

思路

前序遍历算法先访问树的根节点,然后以类似的方式分别遍历左子树和右子树。

方法1——递归

定义函数preorderTraversal(self, node)返回以node为答案的先序遍历结果的数组,假设它的两个孩子node.leftnode.right已经搞定了,即可以返回答案的输出数组。那么思考最终的输出数组是什么样的,很明显要满足根 ➜ 左 ➜ 右的规则,应该返回[node.val] + preorderTraversal(self, node.left) + preorderTraversal(self, node.right)(函数返回的就是一个数组,只需要把它们拼接起来即可)。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root == None:
return []

output = []

output.append(root.val)
output += self.preorderTraversal(root.left)
output += self.preorderTraversal(root.right)

return output
方法2——迭代

递归算法使用系统栈,不好控制,性能问题比较严重,需要进一步了解不用递归如何实现。为了维护固定的访问顺序,使用栈数据结构的先入后出特性。

先处理根节点,根据访问顺序根 ➜ 左 ➜ 右,先入栈的后访问,为了保持访问顺序(先入后出),先把右孩子入栈,再入栈左孩子(此处需要注意,出栈才是访问顺序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root == None:
return []

stack = [root]
output = []

while stack:
root = stack.pop()
if root != None:
# 先入栈右节点
stack.append(root.right)
# 后入栈左节点
stack.append(root.left)
# 栈顶元素并入输出
output.append(root.val)

return output

注意:我这里是把所有迭代过程中的root节点的right节点、left节点(包括空节点)均放入栈,然后在循环里面弹出栈顶元素,检查是否是空,如果为空节点,则不操作。

  • 时间复杂度:访问每个节点恰好一次,时间复杂度为 O(N) ,其中 N 是节点的个数,也就是树的大小。
  • 空间复杂度:取决于树的结构,最坏情况存储整棵树,因此空间复杂度是 O(N)。
方法3——颜色标记法

其核心思想是使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色

  • 如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、左子节点、自身依次入栈。
  • 如果遇到的节点为灰色,则将节点的值输出。

颜色标记法的优势:兼具栈迭代方法的高效,又像递归方法一样简洁易懂,更重要的是,这种方法对于前序、中序、后序遍历,能够写出完全一致的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root == None:
return []

WHITE,GRAY = 0,1
stack = [(WHITE,root)]
output = []

while stack:
color,root = stack.pop()
if root != None:
if color == WHITE:
stack.append((WHITE,root.right))
stack.append((WHITE,root.left))
stack.append((GRAY,root))
else:
output.append(root.val)

return output

94-二叉树的中序遍历

题目描述

给定一个二叉树,返回它的 中序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
1
\
2
/
3

输出: [1,3,2]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

思路

中序遍历的算法先遍历左子树,然后访问根节点,最后遍历右子树,这个算法先尽量移动到树的最左边,然后才开始访问节点。

方法1——递归

同理于前序遍历,一模一样的处理方法,考虑访问顺序为左 ➜ 根 ➜ 右即可,快速模仿并写出代码。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def inorderTraversal(self, root):
if root == None:
return []

output = []

output += self.inorderTraversal(root.left)
output.append(root.val)
output += self.inorderTraversal(root.right)

return output
方法2——迭代

核心思路依旧是利用栈维护节点的访问顺序:左 ➜ 根 ➜ 右。使用一个p_node来指向当前访问节点,p是代表指针point,另外有一个变量cur_node表示当前正在操作节点(把出栈节点值加入输出数组中),算法步骤如下(可以对照代码注释):

  • 访问当前节点,如果当前节点有左孩子,则把它的左孩子都入栈,移动当前节点到左孩子,重复第一步直到当前节点没有左孩子

  • 当当前节点没有左孩子时,栈顶节点出栈,加入结果数组

  • 当前节点指向栈顶节点的右节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
def inorderTraversal(self, root):
if root == None:
return []

stack = []
output = []

# 当前访问节点指针
p_node = root
while stack or p_node:
# 把所有当前访问节点的左孩子都入栈
while p_node:
stack.append(p_node)
p_node = p_node.left

# 操作栈顶节点,如果是第一次运行到这步,那么这是整棵树的最左节点
cur_node = stack.pop()
# 因为已经保证没有左节点,可以访问根节点
output.append(cur_node.val)

if cur_node.right:
# 将指针指向当前节点的右节点
p_node = cur_node.right

return output
方法3——颜色标记法

其核心思想是使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色:

  • 如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈。
  • 如果遇到的节点为灰色,则将节点的值输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def inorderTraversal(self, root):
if root == None:
return []

WHITE,GRAY = 0,1

stack = [(WHITE,root)]
output = []

while stack:
color,root = stack.pop()
if root != None:
if color == WHITE:
stack.append((WHITE,root.right))
stack.append((GRAY,root))
stack.append((WHITE,root.left))
else:
output.append(root.val)

return output

145-二叉树的后序遍历

题目描述

给定一个二叉树,返回它的 后序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]  
1
\
2
/
3

输出: [3,2,1]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

思路

后序遍历算法会先遍历左子树,然后是右子树,最后访问根节点。

方法1——递归

类似前序遍历,只需要改变节点访问顺序

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def postorderTraversal(self,root):
if root == None:
return []

output = []

output += self.postorderTraversal(root.left)
output += self.postorderTraversal(root.right)
output.append(root.val)

return output
方法2——迭代

我们发现后序遍历的顺序是左 ➜ 右 ➜ 根,那么反序的话,就直接倒序的输出结果,即反后序:根 ➜ 右 ➜ 左,和先序遍历的根 ➜ 左 ➜ 右对比,发现只需要稍微改一下代码就可以得到反后序的结果,参考先序遍历,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def postorderTraversal(self,root):
if root == None:
return []

stack = [root]
output = []

while stack:
root = stack.pop()
if root != None:
output.append(root.val)
stack.append(root.left)
stack.append(root.right)

return output[::-1]
方法3——迭代(颜色标记法)

后序遍历访问顺序要求为左 ➜ 右 ➜ 根在对访问节点进行操作的条件是,它的左子树和右子树都已经被访问。这样算法的框架就出来了:只需要对每个节点进行标记,表示这个节点有没有被访问,一个节点能否进行操作的条件就是这个节点的左右节点都被访问过了。

因为栈先入后出,为了维护访问顺序满足条件,入栈顺序应该是根 ➜ 右 ➜ 左(和要求访问顺序相反)。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def postorderTraversal(self,root):
if root == None:
return []

WHITE,GRAY = 0,1

stack = [(WHITE,root)]
output = []

while stack:
color,root = stack.pop()
if root != None:
if color == WHITE:
stack.append((GRAY,root))
stack.append((WHITE,root.right))
stack.append((WHITE,root.left))
else:
output.append(root.val)

return output

以图的广度优先搜索为原型的遍历

102-二叉树的层次遍历

题目描述

给定一个二叉树,返回其按层次遍历的节点值。(即逐层地,从左到右访问所有节点)。

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

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

1
2
3
4
5
[
[3],
[9,20],
[15,7]
]

思路

方法1——借助队列的迭代方法

我们将树上顶点按照层次依次放入队列结构中,队列中元素满足 FIFO(先进先出)的原则。在 Python 中如果使用 Queue 结构,但因为它是为多线程之间安全交换而设计的,所以使用了锁,会导致性能不佳。因此在 Python 中可以使用 deque 的 append()popleft() 函数来快速实现队列的功能。

注意:输出要求List[List[int]]

算法步骤:

  • 计算当前层级节点数目,然后从队列中循环取出当前层级的全部节点(节点放入到列表中),并且将其左右子节点放入队列。
  • 循环上步直到队列为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from collections import deque

class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if root == None:
return []

queue = deque([root,])
output = []

while queue:

# 当前层级节点数目
level_length = len(queue)

temp = []
for _ in range(level_length):
node = queue.popleft()
temp.append(node.val)
if node.left != None:
queue.append(node.left)
if node.right != None:
queue.append(node.right)

output.append(temp)

return output
方法2——递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
# 辅助函数(添加变量res,depth)
def helper(root, res, depth):
if root == None:
return []

# 比较访问节点所在的层次 depth 和当前最高层次 len(res) 的大小,如果前者更大就向 res 添加一个空列表
if len(res) == depth:
res.append([])
# 当前节点插入到对应层的列表 res[depth] 中
res[depth].append(root.val)

# 递归
helper(root.left,res,depth+1)
helper(root.right,res,depth+1)

res = []
helper(root,res,0)
return res
  • 时间复杂度:O(N),因为每个节点恰好会被运算一次。
  • 空间复杂度:O(N),保存输出结果的数组包含 N 个节点的值。

103-二叉树的锯齿形层次遍历

题目描述

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

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

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

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

1
2
3
4
5
[
[3],
[20,9],
[15,7]
]

思路

方法1——借助队列的迭代方法

与102题相同,这道题的本质是树的层次遍历(广度优先遍历)。只需要把偶数层的结果进行反转即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from collections import deque

class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if root == None:
return []

queue = deque([root])
output = []

# 标记是否需要翻转结果
signal = True

while queue:
# 队列的长度(这层的节点数)
length = len(queue)

temp = []

for _ in range(length):
node = queue.popleft()
if node.left != None:
queue.append(node.left)
if node.right != None:
queue.append(node.right)
temp.append(node.val)

# 根据标记决定是否翻转结果
if signal == False:
temp = temp[::-1]
signal = True
else:
signal = False

output.append(temp)

return output

107-二叉树的层次遍历ii

题目描述

给定一个二叉树,返回其节点值自底向上的层次遍历。(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

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

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回其自底向上的层次遍历为:

1
2
3
4
5
[
[15,7],
[9,20],
[3]
]

思路

方法1——层次遍历迭代(反转结果)

我这里用层次遍历得到节点列表,然后将这个节点列表进行反转即可:

1
output = output[::-1]

整体代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import deque

class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if root == None:
return []

queue = deque([root])
output = []

while queue:
# 当前层级节点数目
length = len(queue)
temp = []

for _ in range(length):
node = queue.popleft()
temp.append(node.val)
if node.left != None:
queue.append(node.left)
if node.right != None:
queue.append(node.right)

output.append(temp)

return output[::-1]
方法2——层次遍历迭代(从头添加数组)

当然,我们也可以每次从头添加数组:

1
output.insert(0,temp)

整体代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import deque

class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if root == None:
return []

queue = deque([root])
output = []

while queue:
# 当前层级节点数目
length = len(queue)
temp = []

for _ in range(length):
node = queue.popleft()
temp.append(node.val)
if node.left != None:
queue.append(node.left)
if node.right != None:
queue.append(node.right)

output.insert(0,temp)

return output

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

题目描述

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

1
2
3
4
5
6
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 指针,以指向其下一个右侧节点,如图 B 所示。

提示:

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

思路

方法1——层次遍历-迭代

首先想到层次遍历入队,各层中的点都逐一连接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
"""
# Definition for a Node.
class Node:
def __init__(self, val, left, right, next):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root == None:
return None

queue = [root]
while queue:
length = len(queue)

# 先弹出一个节点,便于循环中填充next指针
pre = queue.pop(0)
# 左右子树入队
if pre.left != None:
queue.append(pre.left)
if pre.right != None:
queue.append(pre.right)

for _ in range(length-1):
cur = queue.pop(0)
pre.next = cur
# 左右子树入队
if cur.left != None:
queue.append(cur.left)
if cur.right != None:
queue.append(cur.right)
# 更新pre指针
pre = cur

return root
方法2——常数空间复杂度

之前是用队列将下一层的节点保存了起来。这里的话,其实只需要提前把下一层的next构造完成,到了下一层的时候就可以遍历了

我们可以通过判断当前遍历的节点是不是null来决定是否进入下一层。

然后,我们需要一个额外的变量存储每一层的开头节点。

下面是一个图解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
"""
# Definition for a Node.
class Node:
def __init__(self, val, left, right, next):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root == None:
return None

start = root
pre = root
cur = root.next

while start.left != None:
# 构造下一层的next指针
pre.left.next = pre.right
while cur != None:
pre.right.next = cur.left
cur.left.next = cur.right
# 更新pre、cur
pre = cur
cur = cur.next

# 更新pre、cur、start
pre = start.left
cur = start.right
start = pre

return root
```

### 117-填充每个节点的下一个右侧节点指针ii
#### 题目描述
给定一个二叉树

```c++
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":null,"next":null,"right":{"$id":"6","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":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}

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

提示:

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

思路

方法1——层次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
"""
# Definition for a Node.
class Node:
def __init__(self, val, left, right, next):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root == None:
return None

queue = [root]
while queue:
length = len(queue)

# 先弹出一个节点,便于循环中填充next指针
pre = queue.pop(0)
# 左右子树入队
if pre.left != None:
queue.append(pre.left)
if pre.right != None:
queue.append(pre.right)

for _ in range(length-1):
cur = queue.pop(0)
pre.next = cur

# 左右子树入队
if cur.left != None:
queue.append(cur.left)
if cur.right != None:
queue.append(cur.right)

pre = cur

return root
方法2——常数空间解法

我们用一个dummy指针,当连接第一个节点的时候,就将dummy指针指向他。

cur 指针利用 next 不停的遍历当前层。如果 cur 的孩子不为 null 就将它接到 tail 后边,然后更新tail。当 cur 为 null 的时候,再利用 dummy 指针得到新的一层的开始节点

下面是一个示意图:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
# Definition for a Node.
class Node:
def __init__(self, val, left, right, next):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
cur = root

while cur != None:
dummy = Node()
tail = dummy

# 遍历cur所在的当前层
while cur != None:
if cur.left != None:
tail.next = cur.left
tail = tail.next

if cur.right != None:
tail.next = cur.right
tail = tail.next

cur = cur.next

# 更新cur到下一层
cur = dummy.next

return root

参考

赞赏一杯咖啡
0%