内容简介:对N叉树进行水平遍历,并输出每一行遍历的结果。这个和一般的水平遍历有所区别,因为它会记录每一行的水平遍历结果分别存在结果数组相应行。因此首先可以用水平遍历的通用解法,即队列的方式,进行解决:
题目要求
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<List<Integer>> levelOrder(Node root) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if(root != null) { LinkedList<Node> queue = new LinkedList<Node>(); queue.offer(root); //下一行的元素数量 int next = 1; List<Integer> levelOrderPerHeight = new ArrayList<Integer>(); 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<Integer>(); next = queue.size(); } } } return result; }
上面的实现中使用next值来记录下一行的元素的个数。但是其实因为结果是采用List<List>的形式来记录的,也就是第i层的水平遍历的结果会记录于数组下标i-1的位置上。因此无需再用队列来额外存储每一行的水平遍历,可以直接通过递归将遍历结果插入到相应行的结果集中。
public List<List<Integer>> levelOrder2(Node root) { List<List<Integer>> result = new ArrayList<List<Integer>>(); levelOrder(root, result, 0); return result; } public void levelOrder(Node root, List<List<Integer>> result, int level) { if(root == null) return; if(level == result.size()) { result.add(new ArrayList<>()); } List<Integer> tmp = result.get(level); tmp.add(root.val); for(Node child : root.children) { levelOrder(child, result, level+1); } }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- leetcode429. N-ary Tree Level Order Traversal
- LeetCode 429 N-ary Tree Level Order Traversal
- Leetcode PHP题解--D55 429. N-ary Tree Level Order Traversal
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
模式识别
(希)Sergios Theodoridis、(希)Konstantinos Koutroumbas / 电子工业出版社 / 2010-2 / 75.00元
本书全面阐述了模式识别的基础理论、最新方法以及各种应用。模式识别是信息科学和人工智能的重要组成部分,主要应用领域有图像分析、光学字符识别、信道均衡、语言识别和音频分类等。本书在完美地结合当前的理论与实践的基础上,讨论了贝叶斯分类、贝叶斯网络、线性和非线性分类器设计、上下文相关分类、特征生成、特征选取技术、学习理论的基本概念以及聚类概念与算法。与前一版相比,增加了大数据集和高维数据相关的最新算法,这......一起来看看 《模式识别》 这本书的介绍吧!