leetcode分类刷题：二叉树（一、简单的层序遍历）

二叉树的深度优先遍历题目是让我有点晕，先把简单的层序遍历总结下吧：配合队列进行的层序遍历在逻辑思维上自然直观，不容易出错

102. 二叉树的层序遍历

本题是二叉树的层序遍历模板：每次循环将一层节点出队，再将一层节点入队，也是所有可用层序遍历解二叉树题目的模板，只需要在模板里稍加改动即可解题

from typing import List, Optional, Union
from collections import deque
'''
102. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1:
    输入：root = [3,9,20,null,null,15,7]
    输出：[[3],[9,20],[15,7]]
题眼：基础
思路：利用队列实现
'''


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:
    if len(nums) == 0:
        return None
    if len(nums) == 1:
        return TreeNode(nums[0])
    # 1、转换为顺序存储
    tmpTree = []
    for n in nums:
        if n != 'null':
            tmpTree.append(TreeNode(n))
        else:
            tmpTree.append(None)
    # 2、转换为链式存储：双指针
    root = tmpTree[0]
    parent, child = 0, 1
    while child < len(tmpTree):
        if tmpTree[parent] != None:  # 双亲节点有效
            if tmpTree[child] != None:  # 左孩子节点有效
                tmpTree[parent].left = tmpTree[child]
            child += 1  # 指向右孩子
            if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子节点存在且有效
                tmpTree[parent].right = tmpTree[child]
            child += 1  # 指向下个节点的左孩子
        parent += 1  # 更新遍历双亲节点
    return root


class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root == None:
            return []
        result = []
        que = deque()
        que.append(root)  # 队列初始值
        while len(que) > 0:
            size = len(que)  # 当前队列长度==二叉树一层的节点个数
            layer = []
            for _ in range(size):  # 一层遍历
                node = que.popleft()  # 记录下出队的节点
                layer.append(node.val)
                # 和之前深度遍历一样：空节点不入队，不然对None节点取值会出错
                if node.left != None:
                    que.append(node.left)
                if node.right != None:
                    que.append(node.right)
            result.append(layer)
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')[1].strip()[1: -1]
            nums = []
            if in_line != '':
                for n in in_line.split(','):
                    if n != 'null':
                        nums.append(int(n))
                    else:
                        nums.append(n)
            root = buildBinaryTree(nums)
            print(obj.levelOrder(root))
        except EOFError:
            break
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85

107. 二叉树的层序遍历 II

“102. 二叉树的层序遍历”的结果反转/逆序即可

from typing import List, Optional, Union
from collections import deque
'''
107. 二叉树的层序遍历 II
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1:
    输入：root = [3,9,20,null,null,15,7]
    输出：[[15,7],[9,20],[3]]
题眼：自底向上的层序遍历
思路：“102. 二叉树的层序遍历”的结果反转/逆序即可
'''


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:
    if len(nums) == 0:
        return None
    if len(nums) == 1:
        return TreeNode(nums[0])
    # 1、顺序存储
    tmpTree = []
    for n in nums:
        if n != 'null':
            tmpTree.append(TreeNode(n))
        else:
            tmpTree.append(None)
    # 2、链式存储：双指针
    root = tmpTree[0]
    parent, child = 0, 1
    while child < len(tmpTree):
        if tmpTree[parent] != None:  # 双亲节点有效
            if tmpTree[child] != None:  # 左孩子有效
                tmpTree[parent].left = tmpTree[child]
            child += 1  # 指向右孩子
            if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子存在且有效
                tmpTree[parent].right = tmpTree[child]
            child += 1  # 指向下个节点的左孩子
        parent += 1
    return root


class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 情况1、树为空
        if root == None:
            return []
        # 情况2、树不为空
        que = deque()
        que.append(root)
        result = []
        while len(que) > 0:
            size = len(que)  # 当前队列长度==二叉树一层的节点个数
            layer = []
            for _ in range(size):  # 一层遍历
                node = que.popleft()
                layer.append(node.val)
                if node.left != None:
                    que.append(node.left)
                if node.right != None:
                    que.append(node.right)
            result.append(layer)
        # 反转result
        # left, right = 0, len(result) - 1
        # while left < right:
        #     result[left], result[right] = result[right], result[left]
        #     left += 1
        #     right -= 1
        return result[::-1]


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')[1].strip()[1: -1]
            nums = []
            if in_line != '':
                for n in in_line.split(','):
                    if n != 'null':
                        nums.append(int(n))
                    else:
                        nums.append(n)
            print(nums)
            root = buildBinaryTree(nums)
            print(obj.levelOrderBottom(root))
        except EOFError:
            break
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

429. N 叉树的层序遍历

一般 层序遍历的基础上，要访问每个节点的N个孩子

from typing import List, Optional, Union
from collections import deque
'''
429. N 叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1:
    输入：root = [1,null,3,2,4,null,5,6]
    输出：[[1],[3,2,4],[5,6]]
题眼：N 叉树的层序遍历
思路：一般 层序遍历的基础上，要访问每个节点的N个孩子
'''


class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children


class Solution:
    def levelOrder(self, root: Node) -> List[List[int]]:
        # 情况1、树为空
        if root == None:
            return []
        # 情况2、树不为空
        que = deque()
        que.append(root)
        result = []
        while len(que) > 0:
            size = len(que)
            layer = []
            for _ in range(size):  # 一层遍历
                node = que.popleft()
                layer.append(node.val)
                if node.children != None:
                    for child in node.children:
                        que.append(child)
            result.append(layer)
        return result
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

637. 二叉树的层平均值

from typing import List, Optional, Union
from collections import deque
'''
637. 二叉树的层平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1:
    输入：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] 。
题眼：每一层节点的平均值
思路：一般 层序遍历的基础上，计算每一层对应的平均值
'''


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:
    if len(nums) == 0:
        return None
    if len(nums) == 1:
        return TreeNode(nums[0])
    # 1、顺序存储
    tmpTree = []
    for n in nums:
        if n != 'null':
            tmpTree.append(TreeNode(n))
        else:
            tmpTree.append(None)
    # 2、转换为链式存储
    root = tmpTree[0]
    parent, child = 0, 1
    while child < len(tmpTree):
        if tmpTree[parent] != None:  # 双亲节点有效
            if tmpTree[child] != None:  # 左孩子节点有效
                tmpTree[parent].left = tmpTree[child]
            child += 1  # 指向右孩子
            if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子存在且有效
                tmpTree[parent].right = tmpTree[child]
            child += 1  # 指向下个节点的左孩子
        parent += 1
    return root


class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        que = deque()
        que.append(root)
        result = []
        while len(que) > 0:
            size = len(que)  # 当前队列长度==二叉树一层的节点个数
            s = 0
            for _ in range(size):  # 一层遍历
                node = que.popleft()
                s += node.val
                if node.left != None:
                    que.append(node.left)
                if node.right != None:
                    que.append(node.right)
            result.append(s / size)
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')[1].strip()[1: -1]
            nums = []
            if in_line != '':
                for n in in_line.split(','):
                    if n != 'null':
                        nums.append(int(n))
                    else:
                        nums.append(n)
            root = buildBinaryTree(nums)
            print(obj.averageOfLevels(root))
        except EOFError:
            break
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
72
73
74
75
76
77
78
79
80
81
82
83
84

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

from typing import List, Optional, Union
from collections import deque
'''
515. 在每个树行中找最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例 1:
    输入: root = [1,3,2,5,3,null,9]
    输出: [1,3,9]
题眼：二叉树的层序遍历
思路：一般 层序遍历的基础上，记录每一行的最大值
'''


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:
    if len(nums) == 0:
        return None
    if len(nums) == 1:
        return TreeNode(nums[0])
    # 1、转换为顺序存储
    tmpTree = []
    for n in nums:
        if n != 'null':
            tmpTree.append(TreeNode(n))
        else:
            tmpTree.append(None)
    root = tmpTree[0]
    # 2、转换为链式存储：双指针
    parent, child = 0, 1
    while child < len(tmpTree):
        if tmpTree[parent] != None:  # 双亲节点有效
            if tmpTree[child] != None:  #  左孩子有效
                tmpTree[parent].left = tmpTree[child]
            child += 1  # 指向右孩子
            if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子存在且有效
                tmpTree[parent].right = tmpTree[child]
            child += 1  # 指向下个节点的左孩子
        parent += 1
    return root


class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        # 情况1、树为空
        if root == None:
            return []
        # 情况2、树不为空
        que = deque()
        que.append(root)
        result = []
        while len(que) > 0:
            size = len(que)  # 当前队列长度==二叉树一层的节点个数
            n = -float('inf')
            for _ in range(size):  # 一层遍历
                node = que.popleft()
                n = max(n, node.val)
                if node.left != None:
                    que.append(node.left)
                if node.right != None:
                    que.append(node.right)
            result.append(n)
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')[1].strip()[1: -1]
            nums = []
            if in_line != '':
                for n in in_line.split(','):
                    if n != 'null':
                        nums.append(int(n))
                    else:
                        nums.append(n)
            root = buildBinaryTree(nums)
            print(obj.largestValues(root))
        except EOFError:
            break
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

199. 二叉树的右视图

一般 层序遍历的基础上，返回每一层的最后一个元素

from typing import List, Optional, Union
from collections import deque
'''
199. 二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
    输入：[1,2,3,null,5,null,4]
    输出：[1,3,4]
题眼：从顶部到底部  从右侧所能看到
思路：一般 层序遍历的基础上，返回每一层的最后一个元素
'''


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:
    if len(nums) == 0:
        return None
    if len(nums) == 1:
        return TreeNode(nums[0])
    # 1、 顺序存储
    tmpTree = []
    for n in nums:
        if n != 'null':
            tmpTree.append(TreeNode(n))
        else:
            tmpTree.append(None)
    # 2、链式存储：双指针
    root = tmpTree[0]
    parent, child = 0, 1
    while child < len(tmpTree):
        if tmpTree[parent] != None:  # 双亲结点有效
            if tmpTree[child] != None:  # 左孩子节点有效
                tmpTree[parent].left = tmpTree[child]
            child += 1  # 指向右孩子
            if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子节点存在且有效
                tmpTree[parent].right = tmpTree[child]
            child += 1  # 指向下个节点的左孩子
        parent += 1
    return root


class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # 情况1、树为空
        if root == None:
            return []
        # 情况2、树不为空
        que = deque()
        que.append(root)
        result = []
        while len(que) > 0:
            size = len(que)
            for i in range(size):  # 一层遍历
                node = que.popleft()
                if i == size - 1:  # 添加每一层的最后一个元素
                    result.append(node.val)
                if node.left != None:
                    que.append(node.left)
                if node.right != None:
                    que.append(node.right)
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip()[1: -1]
            nums = []
            if in_line != '':
                for n in in_line.split(','):
                    if n != 'null':
                        nums.append(int(n))
                    else:
                        nums.append(n)
            root = buildBinaryTree(nums)
            print(obj.rightSideView(root))
        except EOFError:
            break
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85

513. 找树左下角的值

一般 层序遍历的基础上，访问每一层的每个元素时，都把第一个元素进行赋值即可

from typing import List, Optional, Union
from collections import deque
'''
513. 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
    输入: root = [2,1,3]
    输出: 1
题眼：二叉树的层序遍历
思路：一般 层序遍历的基础上，访问每一层的每个元素时，都把第一个元素进行赋值即可
'''


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:
    if len(nums) == 0:
        return None
    if len(nums) == 1:
        return TreeNode(nums[0])
    # 1、顺序存储
    tmpTree = []
    for n in nums:
        if n != 'null':
            tmpTree.append(TreeNode(n))
        else:
            tmpTree.append(None)
    root = tmpTree[0]
    # 2、链式存储
    parent, child = 0, 1
    while child < len(tmpTree):
        if tmpTree[parent] != None:  # 双亲结点有效
            if tmpTree[child] != None:  # 左孩子节点有效
                tmpTree[parent].left = tmpTree[child]
            child += 1  # 指向右孩子
            if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子存在且有效
                tmpTree[parent].right = tmpTree[child]
            child += 1  # 指向下一个节点的左孩子
        parent += 1
    return root


class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        que = deque()
        que.append(root)
        result = 0
        while len(que) > 0:
            size = len(que)
            for i in range(size):
                node = que.popleft()
                if i == 0:  # 总是获取层序遍历的每一层第一个值
                    result = node.val
                if node.left != None:
                    que.append(node.left)
                if node.right != None:
                    que.append(node.right)
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')[1].strip()[1: -1]
            nums = []
            if in_line != '':
                for n in in_line.split(','):
                    if n != 'null':
                        nums.append(int(n))
                    else:
                        nums.append(n)
            root = buildBinaryTree(nums)
            print(obj.findBottomLeftValue(root))
        except EOFError:
            break
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
72
73
74
75
76
77
78
79
80
81
82

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

一般 层序遍历的基础上，对结果的偶数个逆序一下

from typing import List, Optional, Union
from collections import deque
'''
103. 二叉树的锯齿形层序遍历
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1:
    输入：root = [3,9,20,null,null,15,7]
    输出：[[3],[20,9],[15,7]]
题眼：基础
思路：一般 层序遍历的基础上，对结果的偶数个逆序一下
'''


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def buildBinaryTree(nums: List[Union[int, str]]) -> Optional[TreeNode]:
    if len(nums) == 0:
        return None
    if len(nums) == 1:
        return TreeNode(nums[0])
    # 1、转换为顺序存储
    tmpTree = []
    for n in nums:
        if n != 'null':
            tmpTree.append(TreeNode(n))
        else:
            tmpTree.append(None)
    # 2、转换为链式存储：双指针
    root = tmpTree[0]
    parent, child = 0, 1
    while child < len(tmpTree):
        if tmpTree[parent] != None:  # 双亲节点有效
            if tmpTree[child] != None:  # 左孩子节点有效
                tmpTree[parent].left = tmpTree[child]
            child += 1  # 指向右孩子
            if child < len(tmpTree) and tmpTree[child] != None:  # 右孩子节点存在且有效
                tmpTree[parent].right = tmpTree[child]
            child += 1  # 指向下个节点的左孩子
        parent += 1  # 更新遍历双亲节点
    return root


class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 情况1、树为空
        if root == None:
            return []
        # 情况2、树不为空
        que = deque()
        que.append(root)
        result = []
        while len(que) > 0:
            size = len(que)
            layer = []
            for _ in range(size):
                node = que.popleft()
                layer.append(node.val)
                if node.left != None:
                    que.append(node.left)
                if node.right != None:
                    que.append(node.right)
            result.append(layer)
        # 对结果的偶数个逆序一下
        for i in range(1, len(result), 2):
            result[i] = result[i][::-1]
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')[1].strip()[1: -1]
            nums = []
            if in_line != '':
                for n in in_line.split(','):
                    if n != 'null':
                        nums.append(int(n))
                    else:
                        nums.append(n)
            root = buildBinaryTree(nums)
            print(obj.zigzagLevelOrder(root))
        except EOFError:
            break
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

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

一般 层序遍历的基础上，将每层的节点（除最后一个外）的next值指向下一个节点

from typing import List, Optional, Union
from collections import deque
'''
116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有next 指针都被设置为 NULL。
示例 1:
    输入：root = [1,2,3,4,5,6,7]
    输出：[1,#,2,3,#,4,5,6,7,#]
    解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
题眼：二叉树的层序遍历（满二叉树）
思路：一般 层序遍历的基础上，将每层的节点（除最后一个外）的next值指向下一个节点
'''


class Node:
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next


def buildBinartTree(nums: List[Union[int]]) -> Optional[Node]:
    if len(nums) == 0:
        return []
    if len(nums) == 1:
        return Node(nums[0])
    # 1、转换为顺序存储
    tmpTree = []
    for n in nums:
        tmpTree.append(Node(n))
    root = tmpTree[0]
    # 2、转换为链式存储
    parent, child = 0, 1
    while child < len(tmpTree):
        tmpTree[parent].left = tmpTree[child]  # 满二叉树左孩子一定有效
        child += 1
        tmpTree[parent].right = tmpTree[child]  # 满二叉树右孩子一定存在且有效
        child += 1
        parent += 1
    return root


class Solution:
    def connect(self, root: Optional[Node]) -> Optional[Node]:
        # 情况1、树为空
        if root == None:
            return root
        # 情况2、树不为空
        que = deque()
        que.append(root)
        while len(que) > 0:
            size = len(que)
            pre = None
            for i in range(size):
                node = que.popleft()
                if i == 0:  # 记录每层第一个节点为pre
                    pre = node
                else:  # 从每层第二个节点开始，都要给pre的next指针赋值
                    pre.next = node
                    pre = node
                if node.left != None:
                    que.append(node.left)
                if node.right != None:
                    que.append(node.right)
        return root


if __name__ == "__main__":
    while True:
        try:
            in_line = input().strip().split('=')[1].strip()[1: -1]
            nums = []
            if in_line != '':
                for n in in_line.split(','):
                    nums.append(int(n))
            print(nums)
        except EOFError:
            break
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

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

一般 层序遍历的基础上，将每层的节点（除最后一个外）的next值指向下一个节点

from typing import List, Union, Optional
from collections import deque
'''
117. 填充每个节点的下一个右侧节点指针 II
给定一个二叉树
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有next 指针都被设置为 NULL。
示例 1:
    输入：root = [1,2,3,4,5,null,7]
    输出：[1,#,2,3,#,4,5,7,#]
    解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
题眼：二叉树的层序遍历（注意不是满二叉树）
思路：一般 层序遍历的基础上，将每层的节点（除最后一个外）的next值指向下一个节点
'''


class Node:
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next


def buildBinaryTree(nums: List[Union[int, str]]) -> Optional[Node]:
    if len(nums) == 0:
        return None
    if len(nums) == 1:
        return Node(nums[0])
    # 1、转换为顺序存储
    tmpTree = []
    for n in nums:
        if n != 'null':
            tmpTree.append(Node(n))
        else:
            tmpTree.append(None)
    root = tmpTree[0]
    # 2、转换为链式存储
    parent, child = 0, 1
    while child < len(tmpTree):
        if tmpTree[parent] != None:  # 双亲节点有效性判断
            if tmpTree[child] != None:  # 左孩子节点有效性判断
                tmpTree[parent].left = tmpTree[child]
            child += 1
            if child < len(tmpTree) and tmpTree[child] != None:  # 左孩子节点存在且有效
                tmpTree[parent].right = tmpTree[child]
            child += 1
        parent += 1
    return root


class Solution:
    def connect(self, root: Optional[Node]) -> Optional[Node]:
        # 情况1、树为空
        if root == None:
            return root
        # 情况2、树不为空
        que = deque()
        que.append(root)
        while len(que) > 0:
            size = len(que)
            pre = None
            for i in range(size):
                node = que.popleft()
                if i == 0:  # 记录每层第一个节点为pre
                    pre = node
                else:  # 从每层第二个节点开始，都要给pre的next指针赋值
                    pre.next = node
                    pre = node
                if node.left != None:
                    que.append(node.left)
                if node.right != None:
                    que.append(node.right)
        return root


if __name__ == "__main__":
    while True:
        try:
            in_line = input().strip().split('=')[1].strip()[1: -1]
            nums = []
            if in_line != '':
                for n in in_line.split(','):
                    if n != 'null':
                        nums.append(int(n))
                    else:
                        nums.append(n)
            print(nums)
        except EOFError:
            break
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

104. 二叉树的最大深度

思路1、层序遍历：一般 层序遍历的基础上，输出最大高度值
思路2、递归：重复逻辑：二叉树节点的最大深度 等于 左右子树的最大深度+1

'''
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例 1:
    输入：[3,9,20,null,null,15,7]
    输出：3
思路1、层序遍历：一般 层序遍历的基础上，输出最大高度值
思路2、递归：重复逻辑：二叉树节点的最大深度 等于 左右子树的最大深度+1
'''
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # 情况1、树为空
        if root == None:
            return 0
        # 情况2、树不为空
        result = 0
        que = deque()
        que.append(root)
        while len(que) > 0:
            size = len(que)
            for _ in range(size):
                node = que.popleft()
                if node.left != None:
                    que.append(node.left)
                if node.right != None:
                    que.append(node.right)
            result += 1
        return result

    # 重复逻辑：二叉树节点的最大深度 等于 左右子树的最大深度+1
    def maxDepthRecursive(self, root: Optional[TreeNode]) -> int:
        # 1、确定函数参数和返回值
        def maxDepth(node: Optional[TreeNode]) -> int:
            # 2、终止条件
            if node == None:
                return 0
            else:  # 3、单次递归的操作
                leftN = maxDepth(node.left)
                rightN = maxDepth(node.right)
                return max(leftN, rightN) + 1
        return maxDepth(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
36
37
38
39
40
41
42
43

111. 二叉树的最小深度

思路1、层序遍历：一般 层序遍历的基础上，输出最小高度值（第一次遍历到叶子节点的时候）
思路2、递归：重复逻辑：二叉树节点的最小深度 等于 左右子树的最小深度+1，当左右子树不同时存在需要分类讨论

'''
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1:
    输入：root = [3,9,20,null,null,15,7]
    输出：2
思路1、层序遍历：一般 层序遍历的基础上，输出最小高度值（第一次遍历到叶子节点的时候）
思路2、递归：重复逻辑：二叉树节点的最小深度 等于 左右子树的最小深度+1，当左右子树不同时存在需要分类讨论
'''
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        # 情况1、树为空
        if root == None:
            return 0
        # 情况2、树不为空
        result = 0
        que = deque()
        que.append(root)
        while len(que) > 0:
            size = len(que)
            for _ in range(size):
                node = que.popleft()
                if node.left == None and node.right == None:
                    return result + 1
                if node.left != None:
                    que.append(node.left)
                if node.right != None:
                    que.append(node.right)
            result += 1
        return result

    # 重复逻辑：二叉树节点的最小深度 等于 左右子树的最小深度+1，当左右子树不同时存在需要分类讨论
    def minDepthRecursive(self, root: Optional[TreeNode]) -> int:
        # 1、确定函数参数和返回值
        def minD(node: Optional[TreeNode]) -> int:
            # 2、终止条件
            if node == None:
                return 0
            else:  # 3、单次递归的操作
                leftN = minD(node.left)
                rightN = minD(node.right)
                if node.left == None and node.right != None:  # 当一个左子树为空，右不为空，最低高度取决于右子树
                    return rightN + 1
                elif node.left != None and node.right == None:  # 当一个右子树为空，左不为空，最低高度取决于左子树
                    return leftN + 1
                else:
                    return min(leftN, rightN) + 1  # 包含了叶子节点及左右子树都不为空的两种情况
        return minD(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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

559. N 叉树的最大深度

思路1、层序遍历：一般 层序遍历的基础上，输出最大高度值
思路2、递归：重复逻辑：N叉树节点的最大深度 等于 所有子树的最大深度+1

from typing import List, Optional, Union
from collections import deque
'''
559. N 叉树的最大深度
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

示例 1:
    输入：root = [1,null,3,2,4,null,5,6]
    输出：3
题眼：二叉树的层序遍历
思路1、层序遍历：一般 层序遍历的基础上，输出最大高度值
思路2、递归：重复逻辑：N叉树节点的最大深度 等于 所有子树的最大深度+1
'''
class Solution:
    def maxDepth(self, root: 'Node') -> int:  # 递归解法
        if root == None:  # 简单情况
            return 0
        else:  # 重复逻辑：节点的最大高度 等于所有孩子的最大高度+1
            depth = 0
            for child in root.children:
                depth = max(depth, self.maxDepth(child))
            return depth + 1

    def maxDepthIteration(self, root: Optional[Node]) -> int:
        # 情况1、树为空
        if root == None:
            return 0
        # 情况2、树不为空
        result = 0
        que = deque()
        que.append(root)
        while len(que) > 0:
            size = len(que)
            for _ in range(size):
                node = que.popleft()
                if node.children != None:
                    for child in node.children:
                        que.append(child)
            result += 1
        return result
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

222. 完全二叉树的节点个数

本题如果按照普通二叉树来处理，则它的递归解法和“104. 二叉树的最大深度”题目极为类似，连续练习几道递归解法解题之后，递归函数的内部实现和黑盒函数调用区分体会更佳明显了

'''
222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
若最底层为第 h 层，则该层包含 1~2h个节点。
示例 1:
    输入：root = [1,2,3,4,5,6]
    输出：6
思路1、按照普通二叉树求解，“104. 二叉树的最大深度”的相似题目，重复逻辑：二叉树的节点个数等于左右子树的节点个数+1
思路2、利用完全二叉树的性质，判断每个二叉树是否为满二叉树，满二叉树的节点个数等于2^深度-1，不是满二叉树就按照普通二叉树进行处理
'''
class Solution:
    # 思路1、按照普通二叉树求解：迭代法-简单的层序遍历
    def countNodesIteration(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        result = 0
        dq = deque()
        dq.append(root)
        while len(dq) > 0:
            node = dq.popleft()
            result += 1  # 在每次弹出节点后面记录节点个数
            if node.left != None:
                dq.append(node.left)
            if node.right != None:
                dq.append(node.right)
        return result

    # 思路1、按照普通二叉树求解：递归法，重复逻辑：二叉树的节点个数等于左右子树的节点个数+1
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if root == None:  # 终止条件：简单情况
            return 0
        else:  # 重复逻辑
            leftN = self.countNodes(root.left)
            rightN = self.countNodes(root.right)
            return leftN + rightN + 1

    # 思路2、利用完全二叉树的性质：迭代法-简单的层序遍历
    def countNodesIteration2(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        result = 0
        dq = deque()
        dq.append(root)
        while len(dq) > 0:
            node = dq.popleft()
            # 判断node是否是满二叉树：分别求解左右两侧的高度是否相等
            leftN, rightN = 0, 0
            node1, node2 = node, node
            while node1 != None:
                leftN += 1
                node1 = node1.left
            while node2 != None:
                rightN += 1
                node2 = node2.right
            if leftN == rightN:  # 满二叉树
                result += 2 ** leftN - 1
            else:  # 非满二叉树
                result += 1
                if node.left != None:
                    dq.append(node.left)
                if node.right != None:
                    dq.append(node.right)
        return result

    # 思路2、利用完全二叉树的性质：递归法，重复逻辑：判断每个二叉树是否为满二叉树，满二叉树的节点个数等于2^深度-1，不是满二叉树就按照普通二叉树进行处理
    def countNodes2(self, root: Optional[TreeNode]) -> int:
        if root == None:  # 终止条件：简单情况
            return 0
        else:  # 重复逻辑
            leftN, rightN = 0, 0
            node1, node2 = root, root
            while node1 != None:
                leftN += 1
                node1 = node1.left
            while node2 != None:
                rightN += 1
                node2 = node2.right
            if leftN == rightN:  # 满二叉树
                return 2 ** leftN - 1
            else:  # 非满二叉树
                leftN = self.countNodes2(root.left)
                rightN = self.countNodes2(root.right)
                return leftN + rightN + 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
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
72
73
74
75
76
77
78
79
80
81
82
83
84