本文最后更新于：2023年12月5日 下午

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

二叉树中的最大路径和

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

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

给你一个二叉树的根节点 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. 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 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 ，确定它是否是一个 完全二叉树 。

在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 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 ，树中每个节点都存放有一个 0 到 9 之间的数字。

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

  • 例如，从根节点到叶节点的路径 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/

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

微信二维码

微信支付

支付宝二维码

支付宝支付

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