【算法日?！慷鏄涞膶蛹壉闅v

二叉樹的層次遍歷

題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal

題解：

本題有兩種解法，首先第一種肯定是非常明顯的廣度優(yōu)先遍歷，另一種深度優(yōu)先遍歷的解法。

第一種： 廣度優(yōu)先遍歷

廣度優(yōu)先遍歷，將遍歷的每層的結(jié)果放入一個列表中， 該層遍歷結(jié)束，將整個結(jié)果列表加入到總的結(jié)果中即可。
時間復雜度 O(n) 空間復雜度 O(1)(結(jié)果的存儲空間若不進行計算的話)

代碼如下：

import collections

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

# 廣度優(yōu)先遍歷方法
def level_order(root: TreeNode) -> list:
    if not root:
        return []

    queue = collections.deque()  # 申請一個雙端隊列
    queue.append(root)
    result = []

    # visited = set(root)   # 因為是樹的結(jié)構(gòu)，所以只要向下走不會存在重復的情況

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()  # 這里從左邊出了，下面加入的時候就要加到末尾，若是從右邊出，則下面從左邊push進去
            current_level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(current_level)
    return result

if __name__ == '__main__':
    node1 = TreeNode(1)
    node2 = TreeNode(2)
    node3 = TreeNode(3)
    node4 = TreeNode(4)
    node5 = TreeNode(5)
    node6 = TreeNode(6)
    node7 = TreeNode(7)

    node4.left = node2
    node2.left = node1
    node2.right = node3
    node4.right = node6
    node6.left = node5
    node6.right = node7
    print(level_order(node4))

輸出結(jié)果：

 [[4], [2, 6], [1, 3, 5, 7]]

第二種解法：深度優(yōu)先遍歷

進行深度遍歷，將沒個遍歷的節(jié)點，加入到每一層對應的結(jié)果里面
時間復雜度 O(n) 空間復雜度 O(1)(結(jié)果的存儲空間若不進行計算的話)

__代碼如下：___

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

# 依靠深度優(yōu)先遍歷的算法
def level_order(root: TreeNode) -> list:
    if not root:
        return []

    result = []
    level_size = 0
    result = depth_first_search(root, level_size, result)
    return result

def depth_first_search(root, level, result):
    if not root:
        return []

    if len(result) < level + 1:
        result.append([])

    result[level].append(root.val)
    depth_first_search(root.left, level + 1, result)
    depth_first_search(root.right, level + 1, result)
    return result

if __name__ == '__main__':
    node1 = TreeNode(1)
    node2 = TreeNode(2)
    node3 = TreeNode(3)
    node4 = TreeNode(4)
    node5 = TreeNode(5)
    node6 = TreeNode(6)
    node7 = TreeNode(7)

    node4.left = node2
    node2.left = node1
    node2.right = node3
    node4.right = node6
    node6.left = node5
    node6.right = node7
    print(level_order(node4))

輸出結(jié)果：

[[4], [2, 6], [1, 3, 5, 7]]