每日一道算法之--二叉树的层次遍历

递归树的遍历

Word count: 711Reading time: 2 min

 2020/03/03   Share

二叉树的层次遍历

力扣第102题 : https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

例如:

给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7

返回其层次遍历结果：

[
[3],
[9,20],
[15,7]
]

1.递归

一开始看到这题时,因为之前学过二叉树的知识,所以我知道这道题的第一思路就是递归
但是这道层次遍历的主要问题就是,数是分左右节点的,如果直接递归,那么同一层的左右节点就不会给同时读取.所以,能不能先定义一个变量,专门记录该节点的层级.
然后分析题目的返回值,它是一个子元素是列表的列表,不难发现,子元素的索引,刚好就是数的层级,所以可以直接定义一个列表levels = [],每递归一层,如果大列表中没有该层级的子列表,就往大列表中添加一个字列表,然后往该层级的子列表中添加该节点的值
代码如下:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        levels= []
        if not root : return levels
        def foo(node, level):
            n = len(levels)
            if n == level:
                levels.append([])
            levels[level].append(node.val)
            if node.left:
                foo(node.left, level + 1)
            if node.right:
                foo(node.right, level + 1)
        foo(root, 0)
        return levels

1.1 复杂度分析

时间复杂度:假设有n个节点,恰好会递归到每一个节点,所以时间复杂度为O(n)

空间复杂度:假设有n个节点,数组存储的刚好是每一个节点,所以空间复杂度为O(n)

2.迭代

实现了递归的方式后,迭代的思想节本和递归差不多,只是要加多一个栈的数据结构

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        levels = []
        stack = []
        if not root: return levels
        stack.append((root, 0))
        while stack:
            node, level = stack.pop()
            if level == len(levels):
                levels.append([])
            levels[level].append(node.val)
            if node.right:
                stack.append((node.right, level + 1))
            if node.left:
                stack.append((node.left, level + 1))
        return levels