资讯专栏INFORMATION COLUMN

leetcode429. N-ary Tree Level Order Traversal

tomlingtm / 790人阅读

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

题目要求

</>复制代码

  1. Given an n-ary tree, return the level order traversal of its nodes" values. (ie, from left to right, level by level).
  2. For example, given a 3-ary tree:

</>复制代码

  1. We should return its level order traversal:
  2. [
  3. [1],
  4. [3,2,4],
  5. [5,6]
  6. ]
  7. Note:
  8. The depth of the tree is at most 1000.
  9. The total number of nodes is at most 5000.

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

思路和代码

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

</>复制代码

  1. public List> levelOrder(Node root) {
  2. List> result = new ArrayList>();
  3. if(root != null) {
  4. LinkedList queue = new LinkedList();
  5. queue.offer(root);
  6. //下一行的元素数量
  7. int next = 1;
  8. List levelOrderPerHeight = new ArrayList();
  9. while(!queue.isEmpty()) {
  10. next--;
  11. Node tmp = queue.poll();
  12. levelOrderPerHeight.add(tmp.val);
  13. if(tmp.children != null && !tmp.children.isEmpty()) {
  14. for(Node child : tmp.children) {
  15. queue.offer(child);
  16. }
  17. }
  18. //当前行遍历完成,则更新当前行
  19. if(next == 0) {
  20. result.add(levelOrderPerHeight);
  21. levelOrderPerHeight = new ArrayList();
  22. next = queue.size();
  23. }
  24. }
  25. }
  26. return result;
  27. }

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

</>复制代码

  1. public List> levelOrder2(Node root) {
  2. List> result = new ArrayList>();
  3. levelOrder(root, result, 0);
  4. return result;
  5. }
  6. public void levelOrder(Node root, List> result, int level) {
  7. if(root == null) return;
  8. if(level == result.size()) {
  9. result.add(new ArrayList<>());
  10. }
  11. List tmp = result.get(level);
  12. tmp.add(root.val);
  13. for(Node child : root.children) {
  14. levelOrder(child, result, level+1);
  15. }
  16. }

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

转载请注明本文地址: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 评论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 评论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 评论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 评论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 评论0 收藏0

发表评论

0条评论

tomlingtm

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<