LeetCode102-二叉树的层次遍历

本文主要是介绍LeetCode102-二叉树的层次遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode102-二叉树的层次遍历

最近全国疫情严重，待在家里没事干，马上又要准备春招了，最近刷刷题，记录一下！再说一句，武汉加油，大家出门记得戴口罩！

1、题目

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。
示例：

例如:
给定二叉树: [3,9,20,null,null,15,7],3/ \9  20/  \15   7
返回其层次遍历结果：
[[3],[9,20],[15,7]
]

2、思路

递归：
最简单的解法就是递归，首先确认树非空，然后调用递归函数 helper(node, level)，参数是当前节点和节点的层次。程序过程如下：

输出列表称为 levels，当前最高层数就是列表的长度 len(levels)。比较访问节点所在的层次 level 和当前最高层次 len(levels) 的大小，如果前者更大就向 levels 添加一个空列表。
将当前节点插入到对应层的列表 levels[level] 中。
递归非空的孩子节点：helper(node.left / node.right, level + 1)。

迭代：

我们将树上定点按照层次依次放入队列结构中，队列中元素满足FIFO(先进先出)的原则，在JAV阿中可以使用Queue接口中的LinkedList实现。
第 0 层只包含根节点 root ，算法实现如下：

初始化队列只包含一个节点root和层次编号0:level=0
当队列非空的时候：

 - 在输出结果level中插入一个空列表，开始当前层的算法。- 计算当前层有多少个原色：等于队列的长度。- 将这些元素从队列中弹出，并加入levels当前层的空列表中。- 将他们的孩子节点作为下一层压入队列中- 进入下一层level++。

class Solution {
List<List> levels = new ArrayList<List>();
public void bfs(TreeNode node, int level) {
if (levels.size() == level)
levels.add(new ArrayList());
levels.get(level).add(node.val);
if (node.left != null)
bfs(node.left, level + 1);
if (node.right != null)
bfs(node.right, level + 1);
}

    public List<List<Integer>> levelOrder(TreeNode root) {if (root == null) return levels;bfs(root, 0);return levels;}
}

3、代码

基于递归实现：

class Solution {List<List<Integer>> levels = new ArrayList<List<Integer>>();public void bfs(TreeNode node, int level) {if (levels.size() == level)levels.add(new ArrayList<Integer>());levels.get(level).add(node.val);if (node.left != null)bfs(node.left, level + 1);if (node.right != null)bfs(node.right, level + 1);}public List<List<Integer>> levelOrder(TreeNode root) {if (root == null) return levels;bfs(root, 0);return levels;}}

复杂度分析
时间复杂度：O(N)O(N)，因为每个节点恰好会被运算一次。
空间复杂度：O(N)O(N)，保存输出结果的数组包含 N 个节点的值。

迭代

复杂度分析

时间复杂度：O(N)O(N)O(N)，因为每个节点恰好会被运算一次。
空间复杂度：O(N)O(N)O(N)，保存输出结果的数组包含 N 个节点的值。

c++

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int> > res;//A = [[0,1,2],[3,4]]if(!root) return res;//用bfs  搜索 要用队列queue<TreeNode*> q;// start the current levelq.push(root);while(q.size()){// number of elements in the current levelint len=q.size();//存储当前遍历的结果vector<int> level;for(int i=0;i<len;i++){auto t=q.front();q.pop();// fulfill the current levellevel.push_back(t->val);// add child nodes of the current level// in the queue for the next levelif(t->left) q.push(t->left);if(t->right) q.push(t->right);}res.push_back(level);}return res; }
};

Java

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer> > levels=new ArrayList<List<Integer>>();if(root==null) return levels;Queue<TreeNode> queue=new LinkedList<TreeNode>();queue.add(root);int level=0;while(!queue.isEmpty()){levels.add(new ArrayList<Integer>());int level_length=queue.size();for(int i=0;i<level_length;++i){TreeNode node=queue.remove();levels.get(level).add(node.val);if(node.left!=null) queue.add(node.left);if(node.right!=null) queue.add(node.right);}level++;}return levels;}
}