二叉树层次遍历的两种写法-Toy模板网

这篇具有很好参考价值的文章主要介绍了二叉树层次遍历的两种写法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

import collections


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


def nums_to_tree(nums):
    if not nums:
        return None
    queue = collections.deque()
    root = BiTree(nums[0])
    queue.append(root)
    i = 1
    while i < len(nums):
        node = queue.popleft()
        if i < len(nums) and nums[i] != -1:
            node.left = BiTree(nums[i])
            queue.append(node.left)
        i += 1

        if i < len(nums) and nums[i] != -1:
            node.right = BiTree(nums[i])
            queue.append(node.right)
        i += 1

    return root

# 层次遍历
# def level_sort(root):
#     if not root:
#         return None
#     queue = collections.deque()
#     queue.append(root)
#     while len(queue) > 0:  # 只要队不空，出队一个元素，并访问他的孩子节点
#         node = queue.popleft()
#         print(node.val, end="")
#         if node.left:
#             queue.append(node.left)
#         if node.right:
#             queue.append(node.right)


# 层次遍历
def level_sort(root):
    if not root:
        return None
    queue = collections.deque()
    queue.append(root)
    res = []
    while len(queue) > 0:  # 只要队不空，出队一个元素，并访问他的孩子节点
        temp = []
        for i in range(len(queue)):
            node = queue.popleft()
            temp.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(temp)
    print(res)


# 输入 1 null 1 null 1 2
#    1
#  /  \
# null  1
#      /  \
#   null  1
#        /
#       2
if __name__ == '__main__':
    nums = ['1', 'null', '1', 'null', '1', '2']
    nums = [int(i) if i != "null" else -1 for i in nums]
    root = nums_to_tree(nums)
    level_sort(root)