day01 二叉树的层序遍历

题目来源来自于LeetCode,今天的题目是102题:二叉树的层序遍历

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

二叉树的定义:一个节点最多有两个叶子节点的树就叫二叉树。如图:

二叉树结构图

层序遍历是二叉树的一种遍历方式,即逐层地,从左到右地访问所有节点的遍历方法。

看到这道题的时候我第一印象,就是通过队列来实现,依次将父节点入队,然后父节点出队的时候将父节点下的子节点入队,即可返回遍历结果,代码如下:

class Solution:
    def levelOrder(self, root: TreeNode) -> list[list[int]]:
        stack = [root]
        val_list = []
        while len(stack) > 0:
            varnode = stack.pop(0)
            val_list.append(varnode.val)
            print(varnode.val)
            if varnode.left is not None:
                stack.append(varnode.left)
            if varnode.right is not None:
                stack.append(varnode.right)
        return val_list

上面的代码虽然可以正确返回层序遍历的节点顺序,但并不符合这道题的要求,还需要将每一层的代码作为列表去存入,其代码示例为:

示例图

如果需要将每一层都作为单独的一层去存入的话我们可以将每一层的都用一个单独的队列去处理,当父节点队列为空的时候,在将子节点的全部节点入队,其代码如下:

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is not None:
            queue = [root]
            val_list = []
            while len(queue) > 0:
                child_list = []
                node_list = []
                for i in queue:
                    child_list.append(i.val)
                    if i.left is not None:
                        node_list.append(i.left)
                    if i.right is not None:
                        node_list.append(i.right)
                queue = node_list.copy()
                val_list.append(child_list)
            return val_list

用了两个列表来存储变量和节点信息,占用了比较多的额外空间,还有优化的空间。

今天就先到这里,改天写完广度优先遍历之后再来对这道题进行优化。