gpt4 book ai didi

429. N-ary Tree Level Order Traversal N 叉树的层序遍历

转载 作者:大佬之路 更新时间:2024-01-31 14:17:18 28 4
gpt4 key购买 nike

题目地址:https://leetcode.com/problems/n-ary-tree-preorder-traversal/description/

题目描述

Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

Forexample, given a 3-ary tree:

 

Weshould return its level order traversal:

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

Note:

1、 Thedepthofthetreeisatmost1000.;
2、 Thetotalnumberofnodesisatmost5000.;

题目大意

N叉树的层次遍历。

解题方法

方法一:BFS

首先得明白,这个N叉树是什么样的数据结构定义的。val是节点的值,children是一个列表,这个列表保存了其所有节点。

层次遍历比较好理解,就是每层的值保存在一个list中,总的再返回一个list即可。

我们知道这个属于先进先出的结构,其实就是用队列就好了。需要注意是每层都在一个list中,所以在进入队列的时候需要保存一下这个节点属于哪个层。这样当遍历它的时候,就能直接放入它那层的list的末尾即可。难点在维护这个层数。

另外犯了一个小错,当root不存在的时候应该返回的是[],而不是[[]]。

代码如下:

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: Node
        :rtype: List[List[int]]
        """
        if not root:
            return []
        queue = [(root, 0)]
        res = [[]]
        while queue:
            node, level = queue.pop(0)
            if level >= len(res):
                res.append([])
            res[level].append(node.val)
            for child in node.children:
                queue.append((child, level + 1))
        return res

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

二刷,换了一个BFS的写法,我认为下面的这个写法更清晰,而且是个模板,可以直接交套用。

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: Node
        :rtype: List[List[int]]
        """
        res = []
        que = collections.deque()
        que.append(root)
        while que:
            level = []
            size = len(que)
            for _ in range(size):
                node = que.popleft()
                if not node:
                    continue
                level.append(node.val)
                for child in node.children:
                    que.append(child)
            if level:
                res.append(level)
        return res

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

方法二:DFS

实现起来稍微难了一点,因为需要我们根据层数来添加到对应的数组里面去。不过这个比一般的递归简单的地方在于不用考虑root节点的值在什么位置进行添加,因为不在同一层,不会相互影响的。

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: Node
        :rtype: List[List[int]]
        """
        res = []
        self.getLevel(root, res, 0)
        return res
    
    def getLevel(self, root, res, level):
        if not root:
            return []
        if level == len(res):
            res.append([])
        res[level].append(root.val)
        for child in root.children:
            self.getLevel(child, res, level + 1)
        return res

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

参考资料

637. Average of Levels in Binary Treeopen in new window

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com