汉扬编程 编程大纲 打基础之LeetCode算法题第47日:N叉树的层序遍历

打基础之LeetCode算法题第47日:N叉树的层序遍历

一直很纠结算法的文章应该怎么写。最后觉得还是从最简单的level开始写吧,一开始就弄些重量级的,什么人工智能,机器学习的算法,还要有大量的数学以及优化的知识,小白们估计会很郁闷,当然我也不一定能做出来对吧。

打基础之LeetCode算法题第47日:N叉树的层序遍历

我计划每题给出两种语言的解决方案,一种静态语言,一种动态语言。

打基础之LeetCode算法题第47日:N叉树的层序遍历

我选择C语言,Python和Java作为实现语言,由于篇幅有限,其他语言的实现有兴趣的朋友请自己尝试。

打基础之LeetCode算法题第47日:N叉树的层序遍历

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

打基础之LeetCode算法题第47日:N叉树的层序遍历

问题描述:给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。

打基础之LeetCode算法题第47日:N叉树的层序遍历

注:

打基础之LeetCode算法题第47日:N叉树的层序遍历

树的深度不会超过 1000。树的节点总数不会超过 5000。示例:

打基础之LeetCode算法题第47日:N叉树的层序遍历

C++语言实现:树的层序遍历我们可以用广度优先算法来实现。

关于广度优先算法遍历树的问题,我们在之前的问题“第44日”中java和python的实现就用广度优先算法来遍历二叉树。

遍历N叉树和遍历二叉树没有本质上的不同。

层序遍历还可以用递归的方法来实现,实现的方式类似“第44日”中C++的实现。

今天我们解决这个问题的所有实现都是用递归来实现,因为这种实现代码比较精简。关于广度优先算法的实现,大家可以自己尝试写写,有问题可以在评论中提问。

代码1~6行,是优化代码,在“第19日”中有详细说明,这里不再撰述。

在主函数levelOrder中,先定义一个二维vector res,然后调用私有函数doLevelOrder来填充res, 最后返回res。

doLevelOrder函数接受3个产生,第一个是子树的节点,第二个产生就是要填充的二维vector,第三个参数是当前节点在整个树中的层数,我们约定层数从0开始。

doLevelOrder的逻辑:

如果当前是一个空节点,直接返回。如果当前节点不是空节点,那么我们一定会将其val值填充到list中。但是有时候,你要填充的子vector在list中还并不存在,所以我们在第12行做一个判断,这个时候应该为list追加一个空的vector,然后将val填充到里面。

最后对其所有的子节点执行递归,因为是子节点,所以第三个参数即层数要加1。

python语言的实现:python的实现和C++一样也是用递归来实现。

代码如下:

Java语言的实现:Java的实现和C++一样也是用递归来实现。

代码如下:

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/5995.html

编程小白们,别再去啃谭浩强的C语言了,有人这样学一个月入门

求构建一个线性表的完整程序 数据结构C语言版????

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部