leetcode429. N-ary Tree Level Order Traversal

tomlingtm 发布于2019-08-16 16:57 / 790人阅读

摘要：题目要求对叉树进行水平遍历，并输出每一行遍历的结果。因此无需再用队列来额外存储每一行的水平遍历，可以直接通过递归将遍历结果插入到相应行的结果集中。

题目要求

</>复制代码 
Given an n-ary tree, return the level order traversal of its nodes" values. (ie, from left to right, level by level).
For example, given a 3-ary tree:

</>复制代码 
We should return its level order traversal:
[
     [1],
     [3,2,4],
     [5,6]
]
 
Note:
The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

对N叉树进行水平遍历，并输出每一行遍历的结果。

思路和代码

这个和一般的水平遍历有所区别，因为它会记录每一行的水平遍历结果分别存在结果数组相应行。因此首先可以用水平遍历的通用解法，即队列的方式，进行解决：

</>复制代码 
    public List> levelOrder(Node root) {
        List> result = new ArrayList>();
        if(root != null) {
            LinkedList queue = new LinkedList();
            queue.offer(root);
            //下一行的元素数量
            int next = 1;
            List levelOrderPerHeight = new ArrayList();
            while(!queue.isEmpty()) {
                next--;
                Node tmp = queue.poll();
                levelOrderPerHeight.add(tmp.val);
                if(tmp.children != null && !tmp.children.isEmpty()) {
                    for(Node child : tmp.children) {
                        queue.offer(child);
                    }
                }
                //当前行遍历完成，则更新当前行
                if(next == 0) {
                    result.add(levelOrderPerHeight);
                    levelOrderPerHeight = new ArrayList();
                    next = queue.size();
                }
            }
        }
        return result;
    }

上面的实现中使用next值来记录下一行的元素的个数。但是其实因为结果是采用List的形式来记录的，也就是第i层的水平遍历的结果会记录于数组下标i-1的位置上。因此无需再用队列来额外存储每一行的水平遍历，可以直接通过递归将遍历结果插入到相应行的结果集中。

</>复制代码 
    public List> levelOrder2(Node root) { 
        List> result = new ArrayList>();
        levelOrder(root, result, 0);
        return result;
    }
    
    public void levelOrder(Node root, List> result, int level) {
        if(root == null) return;
        if(level == result.size()) {
            result.add(new ArrayList<>());
        }
        List tmp = result.get(level);
        tmp.add(root.val);
        for(Node child : root.children) {
            levelOrder(child, result, level+1);
        }
    }

云服务器 GPU云服务器 Traversal 服务器返回429 Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74290.html

[LeetCode] 429. N-ary Tree Level Order Traversal (

429. N-ary Tree Level Order Traversal Given an n-ary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level). For example, given a 3-ary tree:showImg(https...

LiangJ 2019-08-19 11:18 评论0 收藏0
Leetcode PHP题解--D55 429. N-ary Tree Level Order Tr

摘要：题目链接题目分析按层遍历叉树。思路以层数为键，塞入当前节点的值。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D55 429. N-ary Tree Level Order Traversal 题目链接 429. N-ary Tree Level Order Traversal 题目分析按层遍历N叉树。思路以层数为键，塞入当前节点的值。递归遍历即可。最终代码

libxd 2019-07-01 12:45 评论0 收藏0
[LeetCode] 590. N-ary Tree Postorder Traversal (vs

摘要：按顺序放入，正好方面是从到，顺序方面是从最右到最左，因为是先入后出。这样最后一下就是先左后右，先子后根。 590. N-ary Tree Postorder Traversal Problem Given an n-ary tree, return the postorder traversal of its nodes values.For example, given a 3-ar...

sydMobile 2019-08-19 11:18 评论0 收藏0
[LeetCode] 589. N-ary Tree Preorder Traversal (vs.

589. N-ary Tree Preorder Traversal Given an n-ary tree, return the preorder traversal of its nodes values.For example, given a 3-ary tree:showImg(https://segmentfault.com/img/bVbhKkv?w=781&h=502);Retu...

array_huang 2019-08-19 11:18 评论0 收藏0
Leetcode PHP题解--D43 589. N-ary Tree Preorder Trave

摘要：题目链接题目分析维数组的先序遍历。这题也不想多说什么了。是比较基础的题目了。先序就是先根后子而已。思路在遍历子节点之前，先保存当前节点的信息。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D43 589. N-ary Tree Preorder Traversal 题目链接 589. N-ary Tree Preorder Traversal 题目分析 N维数组的先序遍历。这题也...

junbaor 2019-07-01 12:43 评论0 收藏0