本文最后更新于:2024年1月14日 晚上

学而时习,本文记录树相关算法练习笔记。

二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ,返回其 最大路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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:
res = float("-inf")
def maxPathSum(self, root: Optional[TreeNode]) -> int:

def max_sum_route(node):
if node is None:
return 0

left_max = max(0, max_sum_route(node.left))
right_max = max(0, max_sum_route(node.right))

if left_max + right_max + node.val > self.res:
self.res = left_max + right_max + node.val
cur_max_val = max(0, node.val, node.val + left_max, node.val + right_max)
return cur_max_val
max_sum_route(root)
return self.res

面试题 08.12. 八皇后

设计一种算法,打印 N 皇后在 N × 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
31
32
33
34
35
36
37
class Solution:
total_res_list = list()
def queen_check(self, cur_pair, past_postion):
for past_pair in past_postion:
if past_pair[0] == cur_pair[0]:
return False
if past_pair[1] == cur_pair[1]:
return False
if past_pair[0] - past_pair[1] == cur_pair[0] - cur_pair[1]:
return False
if past_pair[0] + past_pair[1] == cur_pair[0] + cur_pair[1]:
return False
return True

def make_output(self, res_list, n):
str_res_list = list()
for res in res_list:
temp_list = list()
for pos in res:
cur_num = pos[1]
temp_res_str = '.' * cur_num + 'Q' + '.' * (n - cur_num -1)
temp_list.append(temp_res_str)
str_res_list.append(temp_list)
return str_res_list

def solveNQueens(self, n: int) -> List[List[str]]:
self.total_res_list = []
def find_solution(queen_num, past_postion, cur_line):
if cur_line >= queen_num:
self.total_res_list.append(past_postion)
for cur_pos in range(queen_num):
cur_pair = [cur_line, cur_pos]
if self.queen_check(cur_pair, past_postion):
find_solution(queen_num, past_postion + [cur_pair], cur_line + 1)

find_solution(n, [], 0)
return self.make_output(self.total_res_list, n)

2385. 感染二叉树需要的总时间

给你一棵二叉树的根节点 root ,二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟,感染 将会从值为 start 的节点开始爆发。

每分钟,如果节点满足以下全部条件,就会被感染:

  • 节点此前还没有感染。
  • 节点与一个已感染节点相邻。

返回感染整棵树需要的分钟数*。*

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
# 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 amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
start_node_container = []
def add_parent(node, start, start_node_container):
if node is None:
return
if node.val == start:
start_node_container.append(node)
if node.left is not None:
node.left.parent = node
add_parent(node.left, start, start_node_container)
if node.right is not None:
node.right.parent = node
add_parent(node.right, start, start_node_container)
root.parent=None
add_parent(root, start, start_node_container)

start_node = start_node_container[0]

q = [start_node]
visited = {None, start_node}
step = -1

while q:
temp = q
q = []
for node in temp:
if node is not None:
for cur_node in node.left, node.right, node.parent:
if cur_node is not None and cur_node not in visited:
q.append(cur_node)
visited.add(cur_node)
step += 1
return step


572. 另一棵树的子树

给你两棵二叉树 rootsubRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:

def get_tree_list(node, tree_list):
if node is None:
tree_list.append(1e5)
return
tree_list.append(node.val)
get_tree_list(node.left, tree_list)
get_tree_list(node.right, tree_list)

ori_tree_list = list()
get_tree_list(root, ori_tree_list)
ori_str_list = map(lambda x:str(x), ori_tree_list)
ori_str = '_' + '_'.join(ori_str_list) + '_'

sub_tree_list = list()
get_tree_list(subRoot, sub_tree_list)
sub_str_list = map(lambda x:str(x), sub_tree_list)
sub_str = '_' + '_'.join(sub_str_list) + '_'

return sub_str in ori_str

110. 平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
res = [True]
def balance_check(root, res):

if root is None:
return 0
if not res[0]:
return 0
left_depth = balance_check(root.left, res)
right_depth = balance_check(root.right, res)
if abs(left_depth - right_depth) > 1:
res[0] = False
return max(left_depth, right_depth) + 1
balance_check(root, res)
return res[0]

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
cur_node = root
while True:
if p.val == cur_node.val or q.val == cur_node.val:
return cur_node
if p.val < cur_node.val and q.val < cur_node.val:
cur_node = cur_node.left
elif p.val > cur_node.val and q.val > cur_node.val:
cur_node = cur_node.right
else:
return cur_node


111. 二叉树的最小深度

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明:**叶子节点是指没有子节点的节点。

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 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 minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0

q = [root]
cur_level = 0
while True:
temp_q = list()
for node in q:
leaf = True
if node.left is not None:
leaf = False
temp_q.append(node.left)
if node.right is not None:
leaf = False
temp_q.append(node.right)
if leaf:
return cur_level + 1
q = temp_q
cur_level += 1

297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Codec:

def serialize(self, root):
"""Encodes a tree to a single string.

:type root: TreeNode
:rtype: str
"""
res_str_list = list()
q = [root]
while q:
temp_q = list()
for node in q:
if node is None:
res_str_list.append('N')
else:
res_str_list.append(str(node.val))
temp_q.append(node.left)
temp_q.append(node.right)
q = temp_q

res_str = '#'.join(res_str_list)
print(res_str)
return res_str



def deserialize(self, data):
"""Decodes your encoded data to tree.

:type data: str
:rtype: TreeNode
"""
res_str_list = data.split('#')

if res_str_list[0] == 'N':
return None

root = TreeNode(int(res_str_list[0]))
q = [root]
p = 0
left = True
for node_str in res_str_list[1:]:
if node_str == 'N':
cur_node = None
else:
cur_node = TreeNode(int(node_str))
q.append(cur_node)
if left:
q[p].left = cur_node
left = False
else:
q[p].right = cur_node
left = True
p += 1
return root




# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

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
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
p_list = []
q_list = []

cur_list = []

def find_pq_list(node, p, q, p_list, q_list, cur_list):
if node is None:
return

if node == p:
p_list.append(cur_list + [node])
if node == q:
q_list.append(cur_list + [node])

find_pq_list(node.left, p, q, p_list, q_list, cur_list + [node])
find_pq_list(node.right, p, q, p_list, q_list, cur_list + [node])

find_pq_list(root, p, q, p_list, q_list, cur_list)

p_list = p_list[0]
q_list = q_list[0]

length = min(len(p_list), len(q_list))

for index in range(length):
if p_list[index] != q_list[index]:
return p_list[index-1]
if p_list[index] == p or q_list[index] == q:
return p_list[index]

103. 二叉树的锯齿形层序遍历

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

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 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 zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []

q = [root]
res_list = list()

left = True

while q:
temp_q = list()
if left:
res_list.append(list(map(lambda x:x.val, q)))
left = False
else:
res_list.append(list(map(lambda x:x.val, q[::-1])))
left = True

for node in q:
if node.left is not None:
temp_q.append(node.left)
if node.right is not None:
temp_q.append(node.right)

q = temp_q

return res_list

199. 二叉树的右视图

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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]:
if root is None:
return []
q = [root]
res_list = list()
while q:
res_list.append(q[-1].val)
temp_q = list()
for node in q:
if node.left is not None:
temp_q.append(node.left)
if node.right is not None:
temp_q.append(node.right)
q = temp_q
return res_list

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false

叶子节点 是指没有子节点的节点。

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
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
get = [False]

def find_target_path(node, targetSum, sum, get):

if get[0]:
return

if node is None:
return 0

if sum + node.val == targetSum:
if node.left is None and node.right is None:
get[0] = True

find_target_path(node.left, targetSum, sum + node.val, get)
find_target_path(node.right, targetSum, sum + node.val, get)

find_target_path(root, targetSum, 0, get)

return get[0]

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

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
# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
res_list = list()
def cal_sum(node, targetSum, cur_sum, cur_route, res_list):
if node is None:
return

cur_sum = cur_sum + node.val
cur_route = cur_route + [node.val]
if cur_sum == targetSum:
if node.left is None and node.right is None:
res_list.append(cur_route)

cal_sum(node.left, targetSum, cur_sum, cur_route, res_list)
cal_sum(node.right, targetSum, cur_sum, cur_route, res_list)

cal_sum(root, targetSum, 0, [], res_list)
return res_list

958. 二叉树的完全性检验

给定一个二叉树的 root ,确定它是否是一个 完全二叉树

在一个 完全二叉树 中,除了最后一个关卡外,所有关卡都是完全被填满的,并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 12h 节点之间的最后一级 h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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 isCompleteTree(self, root: Optional[TreeNode]) -> bool:

get_none = False
q = [root]
while q:
temp_q = []
for node in q:
if get_none:
if node is not None:
return False
if node is None:
get_none = True
else:
temp_q.append(node.left)
temp_q.append(node.right)
q = temp_q
return True

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def get_bst(nums):
if not nums:
return None
mid_index = len(nums) // 2
cur_node = TreeNode(nums[mid_index])
cur_node.left = get_bst(nums[0:mid_index])
cur_node.right = get_bst(nums[mid_index+1:])
return cur_node
return get_bst(nums)

101. 对称二叉树

给你一个二叉树的根节点 root , 检查它是否轴对称。

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
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
isSym = [True]
def same_check(node1, node2, isSym):
if isSym[0]:
if node1 is None and node2 is None:
return
elif node1 is not None and node2 is not None:
if node1.val != node2.val:
isSym[0] = False
return
else:
same_check(node1.left, node2.right, isSym)
same_check(node1.right, node2.left, isSym)
else:
isSym[0] = False
return
same_check(root.left, root.right, isSym)
return isSym[0]

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树,请找出其中第 k 大的节点的值。

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, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
mid_res = list()
def get_mid_res(node, mid_res):
if node is None:
return
get_mid_res(node.left, mid_res)
mid_res.append(node.val)
get_mid_res(node.right, mid_res)
get_mid_res(root, mid_res)
return mid_res[-k]

剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

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=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
if root is None:
return None
mid_res_list = list()
def get_mid_res(node, mid_res_list):
if node is None:
return
get_mid_res(node.left, mid_res_list)
mid_res_list.append(node)
print(node.val)
get_mid_res(node.right, mid_res_list)

get_mid_res(root, mid_res_list)

print(list(map(lambda x:x.val, mid_res_list)))

for index, node in enumerate(mid_res_list[:-1]):
node.right = mid_res_list[index+1]
mid_res_list[index+1].left = node

mid_res_list[0].left = mid_res_list[-1]
mid_res_list[-1].right = mid_res_list[0]

return mid_res_list[0]

129. 求根节点到叶节点数字之和

给你一个二叉树的根节点 root ,树中每个节点都存放有一个 09 之间的数字。

每条从根节点到叶节点的路径都代表一个数字:

  • 例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123

计算从根节点到叶节点生成的 所有数字之和

叶节点 是指没有子节点的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 sumNumbers(self, root: Optional[TreeNode]) -> int:
sum = [0]
def dfs(node, cur_sum, sum):
if node is None:
return
cur_sum = cur_sum *10 + node.val
if node.left is None and node.right is None:
sum[0] += cur_sum
dfs(node.left, cur_sum, sum)
dfs(node.right, cur_sum, sum)

dfs(root, 0, sum)
return sum[0]

257. 二叉树的所有路径

给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
route_path_list = list()
def dfs(node, cur_route, route_path_list):
if node is None:
return
if cur_route == "":
cur_route += str(node.val)
else:
cur_route += '->' + str(node.val)
if node.left is None and node.right is None:
route_path_list.append(cur_route)
dfs(node.left, cur_route, route_path_list)
dfs(node.right, cur_route, route_path_list)
dfs(root, "", route_path_list)
return route_path_list

114. 二叉树展开为链表

给你二叉树的根结点 root ,请你将它展开为一个单链表:

  • 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 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
# 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 flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
def make_list(node):
if node is None:
return None, None
l_head, l_end = make_list(node.left)
r_head, r_end = make_list(node.right)

node.left = None
end = None
if l_head is None:
if r_head is None:
node.right = None
end = node
else:
node.right = r_head
end = r_end
elif r_head is None:
node.right = l_head
end = l_end
else:
l_end.right = r_head
node.right = l_head
end = r_end
return node, end

make_list(root)

51. N 皇后

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q''.' 分别代表了皇后和空位。

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
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res_list = list()

def check(cur_pos, cur_state):
cur_row = len(cur_state)
for row, state in enumerate(cur_state):
if state == cur_pos:
return False
if cur_row + cur_pos == row + state:
return False
if cur_row - cur_pos == row - state:
return False
return True

def get_anser(n, cur_state, res_list):
if len(cur_state) == n:
res_list.append(cur_state)
return

for cur_pos in range(n):
if check(cur_pos, cur_state):
get_anser(n, cur_state + [cur_pos], res_list)

get_anser(n, [], res_list)

def make_str(pos, n):
return '.' * pos + 'Q' + '.' * (n - pos - 1)

def make_anser(res, n):
return [make_str(pos, n) for pos in res]

return [make_anser(res, n) for res in res_list]


文章链接:
https://www.zywvvd.com/notes/study/algorithm/tree/about-tree/


“觉得不错的话,给点打赏吧 ୧(๑•̀⌄•́๑)૭”

微信二维码

微信支付

支付宝二维码

支付宝支付

算法学习笔记 —— 树
https://www.zywvvd.com/notes/study/algorithm/tree/about-tree/
作者
Yiwei Zhang
发布于
2020年5月21日
许可协议