LeetCodeCampsDay13-二叉树part01

二叉树的遍历,前序/中序/后序/层序,以及迭代、递归等方法实现

二叉树的递归遍历

二叉树的递归遍历,或者说“所有的递归”都离不开三个因素

  1. 确定递归函数的input与output(参数与返回值)
  2. 终止条件
  3. 单层递归的逻辑

以中序遍历为例

  1. 确定递归函数的参数与返回值:

    1. 需要有“当前节点”,其次,需要将中序遍历的结果放在res数组中;可以不返回
    2. def traversal(cur: TreeNode, res: List): ..... return
  2. 终止条件

    1. 当“当前节点”为空时,则终止
    2. if not cur: return
  3. 单层递归的逻辑

    1. 先将"cur.val"添加到res中,再递归遍历"cur.left",最终递归遍历"cur.right"

    2. res.append(cur.val) // 中
      traversal(cur.left, res); // 左
      traversal(cur.right, res); // 右

二叉树的前序遍历

https://leetcode.cn/problems/binary-tree-preorder-traversal/

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例 1:

**输入:**root = [1,null,2,3]

输出:[1,2,3]

解释:

img

示例 2:

**输入:**root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出:[1,2,4,5,6,7,3,8,9]

解释:

img

示例 3:

**输入:**root = []

输出:[]

示例 4:

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

输出:[1]

提示:

  • 树中节点数目在范围 [0, 100]
  • -100 <= Node.val <= 100

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

递归思路

  1. 确定递归函数的输入&输出;确定终止条件;确定单层递归的逻辑
  2. 前序遍历,先记录cur.val,再分别递归左、右子树

递归代码

  • 时间复杂度O(N)
  • 空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
# preorder
def traversal(self, cur: TreeNode, res: List):
if not cur:
return
res.append(cur.val)
self.traversal(cur.left, res)
self.traversal(cur.right, res)

def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
self.traversal(root, res)
return res

迭代思路

  1. 取:中间节点
  2. 处理:将中间节点元素放进result数组中
  3. 访问:遍历子节点

img

迭代代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# 迭代实现
stack = list()
res = list()
if not root:
return res
stack.append(root)
while stack:
# 取中间节点
node = stack.pop()
# 处理:将元素放在res
res.append(node.val)
# 访问:遍历子节点
if node.right: # 加入右节点
stack.append(node.right)
if node.left: # 加入左节点
stack.append(node.left)
return res

统一迭代代码

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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stack = [(root, False)] if root else []
res = list()

while stack:
node, visit_status = stack.pop()
if visit_status:
res.append(node.val)
else:
# 按前序遍历,“中左右”,但这里是栈,所以应该是“右左中”;不过,我决定在最后使用反转大法
# 所以这里还是按“中左右”进行入栈
stack.append((node, True))
if node.left:
stack.append((node.left, False))
if node.right:
stack.append((node.right, False))

res = res[::-1]
return res

二叉树的后序遍历

https://leetcode.cn/problems/binary-tree-postorder-traversal/

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历

示例 1:

**输入:**root = [1,null,2,3]

输出:[3,2,1]

解释:

img

示例 2:

**输入:**root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出:[4,6,7,5,2,9,8,3,1]

解释:

img

示例 3:

**输入:**root = []

输出:[]

示例 4:

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

输出:[1]

提示:

  • 树中节点的数目在范围 [0, 100]
  • -100 <= Node.val <= 100

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

递归代码

  • 时间复杂度O(N)
  • 空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def traversal(self, cur: TreeNode, res: List):
if not cur:
return
self.traversal(cur.left, res) # 左
self.traversal(cur.right, res) # 右
res.append(cur.val)

def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = list()
self.traversal(root, res)
return res

迭代思路

  1. 前序遍历是"中左右",将它换成"中右左",再将res反转就得到了"左右中"(多少是带了技巧的)

img

迭代代码

  • 时间复杂度O(N)
  • 空间复杂度O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# 迭代遍历
stack = list()
res = list()
if not root:
return res
stack.append(root)
while stack:
node = stack.pop()
res.append(node.val)
# 将前序遍历的顺序更换
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
# 最后将结果反转
res = res[::-1]
return res

统一迭代代码

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
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

# 统一迭代遍历
# stack使用bool对每个节点进行标记,False表示没访问过,True则访问过
stack = [(root, False)] if root else []
res = list()

while stack:
node, visit_statue = stack.pop()

# 如果节点已经visited,
if visit_statue:
res.append(node.val)
else:
# 没有访问过这节点,则按后序遍历方式"左右中“”
# 当然也可以使用反转大法,这里就按“左右中”的方式入栈,最后需要将res反转
if node.left: # 左子节点
stack.append((node.left, False))
if node.right: # 右子节点
stack.append((node.right, False))
# 中间节点,注意标记为True
stack.append((node, True))


res = res[::-1]
return res

二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/

给定一个二叉树的根节点 root ,返回 它的 中序 遍历

示例 1:

img

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

示例 2:

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

示例 3:

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

提示:

  • 树中节点数目在范围 [0, 100]
  • -100 <= Node.val <= 100

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

递归代码

  • 时间复杂度O(N)
  • 空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def traversal(self, cur: TreeNode, res: List):
if not cur:
return
self.traversal(cur.left, res) # 左
res.append(cur.val)
self.traversal(cur.right, res) # 右


def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = list()
self.traversal(root, res)
return res

迭代思路

1.中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进result数组中),这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。

img

迭代代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# res = list()
# self.traversal(root, res)
# return res

# 迭代
if not root:
return []
res = list()
stack = list()
cur = root
while cur or stack:
# 先一路干到最底层的左子树节点
if cur:
stack.append(cur)
cur = cur.left
# 到达最左节点后,开始处理栈顶节点
else:
cur = stack.pop()
res.append(cur.val)
# 取栈顶元素右节点
cur = cur.right

return res

统一迭代代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# 统一迭代
stack = [(root, False)] if root else []
res = list()

while stack:
node, visit_status = stack.pop()
if visit_status:
res.append(node.val)
else:
# 按中序遍历,“左中右”,但这里是栈,所以应该是“右中左”;不过,我决定在最后使用反转大法
# 所以这里还是按“左中右”进行入栈
if node.left:
stack.append((node.left, False))
stack.append((node, True))
if node.right:
stack.append((node.right, False))

# 上面为了方便理解,使用left, mid, right的方式进行入栈,最后需要进行反转结果
res = res[::-1]
return res

二叉树的迭代遍历

除了使用递归的方式实现二叉树的遍历,还可以使用“迭代的方法”

递归的本质是:每一次递归调用,都会把函数的局部变量,参数值和返回地址等信息压入调用栈中,等递归返回的时候,从栈顶弹出上一次递归的各项参数

前序遍历(迭代实现)

前序遍历输出“中,左,右”,所以需要先将“中间”节点放在栈中,然后弹出,并将右孩子入栈,再加入左孩子(因为后入先出,左孩子得先出,所以得后入)

img

二叉树的统一迭代

标记法

加一个 boolean 值跟随每个节点,false (默认值) 表示需要为该节点和它的左右儿子安排在栈中的位次,true 表示该节点的位次之前已经安排过了,可以收割节点了。

这种方法可以叫做boolean 标记法, 这种方法更容易理解,在面试中更容易写出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# stack的初始化
# 其中的False表示这个节点没有访问过,需要给这个节点以及它的左、右两个节点安排位置
stack = [(root, False)] if root else []
res = list()
#
while stack:
# 弹出一个节点进行visit状态的判断
node, visit_status = stack.pop()

# 如果已经visited过,说明可以收割了,将node结果放在res里
if visit_status:
res.append(node.val)
else:
# 下面就是按“既定顺序”添加到stack中即可
# 比如前序就是“中左右”
stack.append((node, True))
if node.left:
stack.append((node.left, False))
if node.right:
stack.append((node.right, False))

# 由于res是个栈,而上面添加到栈的顺序是按“既定顺序”添加的,而实际输出需要进行反转(因为栈是先入后出)
res = res[::-1]

空指针法

就是要处理的节点放入栈之后,紧接着放入一个空指针作为标记。 这种方法可以叫做空指针标记法

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]:
result = []
st= []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
if node.right: #右
st.append(node.right)
if node.left: #左
st.append(node.left)
st.append(node) #中
st.append(None)
else:
node = st.pop()
result.append(node.val)
return result

层序遍历

之前的前/中/后序遍历都使用了栈/递归的思想(本质是深度优先遍历),而层序遍历是广度优先遍历,如果提到广度优先,就需要使用队列了

队列先进先出,符合一层一层遍历的逻辑,而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

img

代码

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

queue = deque()
res = list()
queue.append(root)
while queue:
# level记录的是每层的结果
level = list()
L = len(queue)
# 注意这里的L不会跟着queue增加或减少而变化
for i in range(L):
cur = queue.popleft()

level.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
# 最终将每层的结果汇总到res中
res.append(level)

return res

102. 二叉树的层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/

提示

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

示例 1:

img

1
2
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]

示例 2:

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

示例 3:

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

提示:

  • 树中节点数目在范围 [0, 2000]
  • -1000 <= Node.val <= 1000

迭代法思路

  1. 队列先进先出,符合一层一层遍历的逻辑,而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
  2. 层序遍历有两个可以操作的位置,分别是每次弹出一个node后;以及每层的清算

img

迭代法代码

  • 时间复杂度O(N)
  • 空间复杂度O(N)
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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from collections import deque
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
res = list()
queue = deque()
queue.append(root)

while queue:
level_res = list()
# 操作位置1
L = len(queue)
for i in range(L):
node = queue.popleft()
level_res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 操作位置2 (每层的清算)
res.append(level_res)

return res

递归法

  • 时间复杂度O(N)
  • 空间复杂度O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
# 确定好输入与输出
def traverse(self, node, level, levels):
# 终止条件
if not node:
return
# 单次递归做的事儿
# 这里表示,需要给levels添加一个新level,用来装新level的数据
if len(levels) == level:
levels.append([])
# 注意,这里使用的是levels[level]
levels[level].append(node.val)
self.traverse(node.left, level + 1, levels)
self.traverse(node.right, level + 1, levels)

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []

levels = list()

self.traverse(root, 0, levels)
return levels

二叉树的层序遍历 II

https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/

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

示例 1:

img

1
2
输入:root = [3,9,20,null,null,15,7]
输出:[[15,7],[9,20],[3]]

示例 2:

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

示例 3:

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

提示:

  • 树中节点数目在范围 [0, 2000]
  • -1000 <= Node.val <= 1000

代码

  • 时间复杂度O(N)
  • 空间复杂度O(N)
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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
# 把res数组反转下就好
from collections import deque
if not root:
return []
queue = deque()
res = list()
queue.append(root)

while queue:
level_res = list()
L = len(queue)
for _ in range(L):
node = queue.popleft()
level_res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level_res)
# 将res结果反转即可
return res[::-1]

199. 二叉树的右视图

https://leetcode.cn/problems/binary-tree-right-side-view/

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

示例 1:

**输入:**root = [1,2,3,null,5,null,4]

输出:[1,3,4]

解释:

img

示例 2:

**输入:**root = [1,2,3,4,null,null,null,5]

输出:[1,3,4,5]

解释:

img

示例 3:

**输入:**root = [1,null,3]

输出:[1,3]

示例 4:

**输入:**root = []

输出:[]

提示:

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

思路

  1. 在层序遍历基础上,将level_res替换成只记录一个值(只记录当前层的最后一个节点)

代码

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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
# 层序遍历,但规则是:只遍历这层最后一个节点
from collections import deque
if not root:
return []
queue = deque()
res = list()
queue.append(root)

while queue:
# level_res其实只要保持一个节点即可
level_res = None
L = len(queue)
for _ in range(L):
node = queue.popleft()
# 用这层新节点替换掉之前的结果,保证level_res只记录当前层最后一个节点
level_res = node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level_res)
return res

思路二

  1. 判断当前循环是否是当前层最后一个,如果是,则记录

代码二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
from collections import deque
if not root:
return []
queue = deque()
res = list()
queue.append(root)

while queue:
L = len(queue)
for i in range(L):
node = queue.popleft()
# 如果是当前层最后一个,才记录
if i == L - 1:
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res

二叉树的层平均值

https://leetcode.cn/problems/average-of-levels-in-binary-tree/

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

示例 1:

img

1
2
3
4
输入:root = [3,9,20,null,null,15,7]
输出:[3.00000,14.50000,11.00000]
解释:第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

示例 2:

img

1
2
输入:root = [3,9,20,15,7]
输出:[3.00000,14.50000,11.00000]

提示:

  • 树中节点数量在 [1, 104] 范围内
  • -231 <= Node.val <= 231 - 1

思路

在层序的基础上记录每层的总和与个数,再求个均值即可

代码

  • 时间复杂度O(N)
  • 空间复杂度O(W)—取决于二叉树的最大宽度
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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
from collections import deque

que = deque()
if not root:
return []
que.append(root)
res = []
while que:
L = len(que)
levelsum = 0
count = 0
for i in range(L):
node = que.popleft()
levelsum += node.val
count += 1
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
res.append(levelsum/count)
return res

429. N 叉树的层序遍历

https://leetcode.cn/problems/n-ary-tree-level-order-traversal/

给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。

树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。

示例 1:

img

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

示例 2:

img

1
2
输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示:

  • 树的高度不会超过 1000
  • 树的节点总数在 [0, 104] 之间

代码

  • 时间复杂度O(N)—每个元素遍历一次
  • 空间复杂度O(W)—取决于二叉树的最大宽度
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
"""
# Definition for a Node.
class Node:
def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
self.val = val
self.children = children
"""

class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
from collections import deque
que = deque()
if not root:
return []
que.append(root)
res = list()
while que:
L = len(que)
levelList = list()
for i in range(L):
node = que.popleft()
levelList.append(node.val)
for eachNode in node.children:
que.append(eachNode)
res.append(levelList)
return res

515. 在每个树行中找最大值

https://leetcode.cn/problems/find-largest-value-in-each-tree-row/

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

示例1:

img

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

示例2:

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

提示:

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

代码

  • 时间复杂度O(N)
  • 空间复杂度O(w)
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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
from collections import deque

que = deque()
if not root:
return []
que.append(root)
res = []
while que:
L = len(que)
levelMax = None
for i in range(L):
node = que.popleft()
if levelMax is None:
levelMax = node.val
else:
levelMax = max(levelMax, node.val)
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
res.append(levelMax)
return res

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

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/

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

1
2
3
4
5
6
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL

初始状态下,所有 next 指针都被设置为 NULL

示例 1:

img

1
2
3
输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,'#' 标志着每一层的结束。

示例 2:

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

提示:

  • 树中节点的数量在 [0, 212 - 1] 范围内
  • -1000 <= node.val <= 1000

进阶:

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

思路

  1. 使用层序遍历,将每个节点保存在levelList里,在每层结算时,将levelList节点串起来

代码

  • 时间复杂度O(N)
  • 空间复杂度O(w)
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
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""

class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
from collections import deque

que = deque()
if not root:
return
que.append(root)

while que:
L = len(que)
levelList = list()
for i in range(L):
node = que.popleft()
levelList.append(node)
# 添加下一层到队列
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
# 将这层串起来
for i in range(len(levelList) - 1):
levelList[i].next = levelList[i+1]

return root

或者使用一个pre节点,记录前一个值,再令pre.next = node即可

  • 时间复杂度O(N)
  • 空间复杂度O(W)
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
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""

class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
from collections import deque

que = deque()
if not root:
return
que.append(root)

while que:
L = len(que)
nodePrev = None
for i in range(L):
node = que.popleft()
if nodePrev:
nodePrev.next = node
nodePrev = node
# 添加下一层到队列
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)

return root