Binary Tree Level Order

Table of Contents

• 199. Binary Tree Right Side View (Medium)
• 637. Average of Levels in Binary Tree (Easy)
• 102. Binary Tree Level Order Traversal (Medium)
• 103. Binary Tree Zigzag Level Order Traversal (Medium)

199. Binary Tree Right Side View

• LeetCode | 力扣

• Tags: Tree, Depth First Search, Breadth First Search, Binary Tree

Python

from collections import deque
from typing import List, Optional

from binarytree import Node as TreeNode
from binarytree import build


# Binary Tree BFS
def rightSideViewBFS(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []

    q = deque([root])
    res = []

    while q:
        n = len(q)
        for i in range(n):
            node = q.popleft()
            if i == n - 1:
                res.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

    return res


# Binary Tree DFS
def rightSideViewDFS(root: Optional[TreeNode]) -> List[int]:
    """后序遍历，先右后左，遇到的第一个节点就是该深度的最右侧节点"""
    ans = []

    def dfs(node, depth):
        if node is None:
            return
        if depth == len(ans):  # 这个深度首次遇到
            ans.append(node.val)

        dfs(node.right, depth + 1)
        dfs(node.left, depth + 1)

    dfs(root, 0)

    return ans


if __name__ == "__main__":
    root = [1, 2, 2, 3, 4, None, 3, None, None, 5]
    root = build(root)
    print(root)
    #     ____1
    #    /     \
    #   2__     2
    #  /   \     \
    # 3     4     3
    #      /
    #     5
    assert rightSideViewBFS(root) == [1, 2, 3, 5]
    assert rightSideViewDFS(root) == [1, 2, 3, 5]

637. Average of Levels in Binary Tree

• LeetCode | 力扣

• Tags: Tree, Depth First Search, Breadth First Search, Binary Tree

Python

from collections import deque
from typing import List, Optional

from binarytree import Node as TreeNode
from binarytree import build


# Binary Tree BFS
def averageOfLevels(root: Optional[TreeNode]) -> List[float]:
    if not root:
        return []

    q = deque([root])
    res = []

    while q:
        n = len(q)
        level = 0
        for _ in range(n):
            cur = q.popleft()
            level += cur.val

            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)

        res.append(float(level / n))

    return res


if __name__ == "__main__":
    root = [3, 9, 20, None, None, 15, 7]
    root = build(root)
    print(root)
    #   3___
    #  /    \
    # 9     _20
    #      /   \
    #     15    7
    assert averageOfLevels(root) == [3.00000, 14.50000, 11.00000]

102. Binary Tree Level Order Traversal

• LeetCode | 力扣

• Tags: Tree, Breadth First Search, Binary Tree

Python

from collections import deque
from typing import List, Optional

from binarytree import Node as TreeNode
from binarytree import build


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

    q = deque([root])
    res = []

    while q:
        level = []
        size = len(q)

        for _ in range(size):
            cur = q.popleft()
            level.append(cur.val)

            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)

        res.append(level)

    return res


tree = build([3, 9, 20, None, None, 15, 7])
print(tree)
#   3___
#  /    \
# 9     _20
#      /   \
#     15    7
print(levelOrder(tree))  # [[3], [9, 20], [15, 7]]

103. Binary Tree Zigzag Level Order Traversal

• LeetCode | 力扣

• Tags: Tree, Breadth First Search, Binary Tree

Python

from collections import deque
from typing import List, Optional

from binarytree import Node as TreeNode
from binarytree import build


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

    q = deque([root])
    res = []

    while q:
        level = []
        size = len(q)

        for _ in range(size):
            cur = q.popleft()
            level.append(cur.val)

            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)

        res.append(level if not len(res) % 2 else level[::-1])

    return res


if __name__ == "__main__":
    tree = build([3, 9, 20, None, None, 15, 7])
    print(tree)
    #   3___
    #  /    \
    # 9     _20
    #      /   \
    #     15    7
    assert zigzagLevelOrder(tree) == [[3], [20, 9], [15, 7]]

Comments