【基础算法精讲-学习记录】二叉树5

视频学习记录

https://www.bilibili.com/video/BV1hG4y1277i?

• 层序遍历，在二叉树中也能叫BFS，与DFS相比，核心就是从上往下一层层地遍历二叉树。

• 一种实现方式是准备两个数组，cur和nxt分别存放当前要遍历的节点和下一层的节点，一轮轮遍历。

• 另一种不用nxt数组，下一层的节点直接放在cur后面（cur当队列用），遍历每一层节点时注意当前层的节点数目来遍历。

例题和课后作业代码记录

102. 二叉树的层序遍历

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

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：On，姑且也是会在最差的情况下，存储半个树节点到vals
        if not root:
            return []
        cur = deque([root])
        ans = []
        while cur:
            vals = []
            # print(cur, len(cur))
            for _ in range(len(cur)):
                node = cur.popleft()
                vals.append(node.val)
                if node.left:
                    cur.append(node.left)
                if node.right:
                    cur.append(node.right)
            ans.append(vals)
        return ans

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

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

# 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]]:
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：On，姑且也是会在最差的情况下，存储半个树节点到vals
        if not root:
            return []
        cur = deque([root])
        ans = []
        even = False # 对于偶数行，做反转
        while cur:
            vals = []
            # print(cur, len(cur))
            for _ in range(len(cur)):
                node = cur.popleft()
                vals.append(node.val)
                if node.left:
                    cur.append(node.left)
                if node.right:
                    cur.append(node.right)
            if even:
                ans.append(vals[::-1])
            else:
                ans.append(vals)
            even = not even
        return ans

513. 找树左下角的值

https://leetcode.cn/problems/find-bottom-left-tree-value/description/

# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：Oh，h为树的高度
        if not root:
            return []
        cur = deque([root])
        ans = []
        while cur:
            vals = []
            # print(cur, len(cur))
            for _ in range(len(cur)):
                node = cur.popleft()
                if len(vals) == 0:
                    vals.append(node.val)
                if node.left:
                    cur.append(node.left)
                if node.right:
                    cur.append(node.right)
            ans.append(vals[0])
        return ans[-1]

107. 二叉树的层序遍历 II

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

# 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]]:
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：On，姑且也是会在最差的情况下，存储半个树节点到vals
        if not root:
            return []
        cur = deque([root])
        ans = []
        while cur:
            vals = []
            # print(cur, len(cur))
            for _ in range(len(cur)):
                node = cur.popleft()
                vals.append(node.val)
                if node.left:
                    cur.append(node.left)
                if node.right:
                    cur.append(node.right)
            ans.append(vals)
        return ans[::-1]

104. 二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        # 层序遍历解法：
        # 时间：遍历所有节点 On
        # 空间：Oh，h是树的高度
        if not root:
            return 0
        cur = deque([root])
        ans = 0
        while cur:
            # print(cur, len(cur))
            for _ in range(len(cur)):
                node = cur.popleft()
                if node.left:
                    cur.append(node.left)
                if node.right:
                    cur.append(node.right)
            ans += 1
        return ans

        # 下面是dfs的解法
        # 时间：遍历所有节点 On
        # 空间：最坏情况下，节点都在单边，On
        if not root:
            return 0 
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

111. 二叉树的最小深度

https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

# 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:
        # 层序遍历方法
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：On，姑且也是会在最差的情况下，存储半个树节点到vals
        if not root:
            return 0
        cur = deque([root])
        ans = 0
        end = False
        while cur and not end:
            ans += 1
            for _ in range(len(cur)):
                node = cur.popleft()
                son_cnt = 0
                if node.left:
                    cur.append(node.left)
                    son_cnt += 1
                if node.right:
                    cur.append(node.right)
                    son_cnt += 1
                if son_cnt == 0: # 找到第一个叶子节点就马上截断
                    end = True
                    break
        return ans

        # 下面是dfs方法
        # 时间：遍历所有节点 On
        # 空间：最坏情况下，节点都在单边，On
        # 由于答案只能来源于非空的一侧，所以逻辑比取最大复杂一些
        if not root:
            return 0
        if not root.left and not root.right:
            return 1 # 必须得是叶子节点才能算好的
        if not root.left:
            return self.minDepth(root.right)+1
        elif not root.right:
            return self.minDepth(root.left)+1
        else:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

2583. 二叉树中的第 K 大层和

https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/description/

# 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 kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：On，姑且也是会在最差的情况下，存储半个树节点到vals
        if not root:
            return []
        cur = deque([root])
        ans = []
        while cur:
            val = 0
            # print(cur, len(cur))
            for _ in range(len(cur)):
                node = cur.popleft()
                val += node.val
                if node.left:
                    cur.append(node.left)
                if node.right:
                    cur.append(node.right)
            ans.append(val)
        ans.sort()
        return ans[-k]

199. 二叉树的右视图

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

# 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]:
        # 层序遍历解法
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：On，姑且也是会在最差的情况下，存储半个树节点到vals
        if not root:
            return []
        cur = deque([root])
        ans = []
        while cur:
            right_node = -101
            # print(cur, len(cur))
            for _ in range(len(cur)):
                node = cur.popleft()
                if right_node == -101:
                    right_node = node.val
                if node.right:
                    cur.append(node.right)
                if node.left:
                    cur.append(node.left)
                
            ans.append(right_node)
        return ans

        # 下面是dfs解法
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，On
        ans = []
        def dfs(root: Optional[TreeNode], carry:int):
            if not root:
                return 
            nonlocal ans 
            if carry >= len(ans):
                ans.append(root.val)
            carry += 1
            dfs(root.right, carry)
            dfs(root.left, carry)
        dfs(root, 0)
        return ans

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

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

"""
# 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]':
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：On，姑且也是会在最差的情况下，存储半个树节点到vals
        if not root:
            return root
        cur = deque([root])
        # ans = []
        while cur:
            # vals = []
            # print(cur, len(cur))
            connect_next_cnt = len(cur)-1 # 由于确定是完美二叉树，所以每层要连接的数量就是比节点数量少1
            for _ in range(len(cur)):
                node = cur.popleft()
                # vals.append(node.val)
                if node.left:
                    cur.append(node.left)
                if node.right:
                    cur.append(node.right)
                if connect_next_cnt > 0:
                    connect_next_cnt -= 1
                    node.next = cur[0]
            # ans.append(vals)
        return root

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

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

"""
# 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: 'Node') -> 'Node':
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：On，姑且也是会在最差的情况下，存储半个树节点到vals
        if not root:
            return root
        cur = deque([root])
        # ans = []
        while cur:
            # vals = []
            # print(cur, len(cur))
            connect_next_cnt = len(cur)-1 # 由于确定是完美二叉树，所以每层要连接的数量就是比节点数量少1
            for _ in range(len(cur)):
                node = cur.popleft()
                # vals.append(node.val)
                if node.left:
                    cur.append(node.left)
                if node.right:
                    cur.append(node.right)
                if connect_next_cnt > 0:
                    connect_next_cnt -= 1
                    node.next = cur[0]
            # ans.append(vals)
        return root

1302. 层数最深叶子节点的和

https://leetcode.cn/problems/deepest-leaves-sum/description/

# 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 deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：On，姑且也是会在最差的情况下，存储快半个树节点到cur
        if not root:
            return 0
        cur = deque([root])
        ans = 0
        while cur:
            vals = 0
            # print(cur, len(cur))
            for _ in range(len(cur)):
                node = cur.popleft()
                vals += node.val
                if node.left:
                    cur.append(node.left)
                if node.right:
                    cur.append(node.right)
            ans = vals
        return ans

1609. 奇偶树

https://leetcode.cn/problems/even-odd-tree/description/

# 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 isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：On，姑且也是会在最差的情况下，存储半个树节点到vals
        cur = deque([root])
        # ans = True
        even = True # 这里是从0层开始
        end = False
        while cur and not end:
            vals = []
            for _ in range(len(cur)):
                node = cur.popleft()
                x = node.val
                if even:
                    if x % 2 == 0:
                        end = True 
                        break
                    elif vals and x <= vals[-1]:
                        end = True 
                        break 
                else: 
                    if x % 2 == 1:
                        end = True 
                        break
                    elif vals and x >= vals[-1]:
                        end = True 
                        break 

                vals.append(x)
                if node.left:
                    cur.append(node.left)
                if node.right:
                    cur.append(node.right)
            even = not even
        return not end # 如果有提前终止，就是相当于有不符合的地方

2415. 反转二叉树的奇数层

https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/description/

# 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 reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：On，姑且也是会在最差的情况下，存储半个树节点到vals
        # 这题如果用两个数组轮换应该更快点，对于奇数层列就左右遍历翻转，不用记录值还翻转
        if not root:
            return []
        cur = deque([root])
        ans = []
        even = True
        while cur:
            vals = []
            to_reverse_node = []

            for _ in range(len(cur)):
                node = cur.popleft()
                vals.append(node.val)
                if node.left:
                    cur.append(node.left)
                if node.right:
                    cur.append(node.right)
                if not even:
                    to_reverse_node.append(node)

            for node, new_val in zip(to_reverse_node, vals[::-1]):
                node.val = new_val

            even = not even
        return root

2641. 二叉树的堂兄弟节点 II

https://leetcode.cn/problems/cousins-in-binary-tree-ii/description/

# 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 replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 时间：On，遍历了整棵树，不过是层序遍历
        # 空间：On，姑且也是会在最差的情况下，存储半个树节点到vals
        # 对于本题的每一层，可以按父节点分成不同list，求总和，总和减去自己节点的和就是所有堂兄弟的和
        if not root:
            return []
        cur = [[root]]
        ans = []
        while cur:
            nxt = []
            vals = []
            row_sum = 0
            # print(cur, len(cur))
            for tmp_pair in cur: # 记录行值总和和上个父节点每节的和
                tmp_pair_vals = []
                for node in tmp_pair:
                    tmp_pair_vals.append(node.val)
                    row_sum += node.val
                    tmp_pair = []
                    if node.left:
                        tmp_pair.append(node.left)
                    if node.right:
                        tmp_pair.append(node.right)
                    nxt.append(tmp_pair)
                vals.append(sum(tmp_pair_vals))
            
            for tmp_pair, pair_val in zip(cur, vals): # 更新值
                new_val = row_sum - pair_val
                for node in tmp_pair:
                    node.val = new_val 
            
            cur = nxt
        return root