102. Binary Tree Level Order Traversal(C++和Java实现二叉树层序遍历)

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

return its level order traversal as:

[ [3], [9,20], [15,7] ]

 关键思路：常规二叉树层序遍历用队列即可，但该题需要记录每一层有多少个节点

解法一：

二叉树先序遍历和层序号level_num结合，每当遍历某个节点的左右孩子时，将level_num + 1。通过map记录要求的结果，其中key代表层序号，value为该层包含的节点数组。

C++版本

class Solution { public: map<int, vector<int>> level; void preOrder(TreeNode* node, int level_num){ if(node != NULL){ level[level_num].push_back(node->val); preOrder(node->left, level_num + 1); preOrder(node->right, level_num + 1); } } vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; preOrder(root, 1); for(auto v: level){ result.push_back(v.second); } return result; } };

Java版本

Map<Integer, List<Integer>> level = new HashMap<>(); void preOrder(TreeNode node, int level_num){ if(node != null){ if(level.containsKey(level_num)){ level.get(level_num).add(node.val); } else{ List<Integer> l = new ArrayList<>(); l.add(node.val); level.put(level_num, l); } preOrder(node.left, level_num + 1); preOrder(node.right, level_num + 1); } } public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); preOrder(root, 1); for(Integer i: level.keySet()){ result.add(level.get(i)); } return result; }

解法二：

利用队列进行层序遍历，并且通过level_size记录二叉树某层共多少个节点，因为层序遍历的特点就是遍历完某一层的最后一个阶段，队列的size就是下一层节点数量，具体见代码。

class Solution { public: map<int, vector<int>> level; void preOrder(TreeNode* node, int level_num){ if(node != NULL){ level[level_num].push_back(node->val); preOrder(node->left, level_num + 1); preOrder(node->right, level_num + 1); } } vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; int level_size = 0; queue<TreeNode*> q; if(root != NULL){ q.push(root); } TreeNode* node; while(!q.empty()){ vector<int> level; //存储当前层的节点 level_size = q.size(); //代表当前层节点数量 while(level_size--){ //一直操作完当前层的节点 node = q.front(); q.pop(); level.push_back(node->val); //左右孩子都属于下一层，如队列 if(node->left != NULL){ q.push(node->left); } if(node->right != NULL){ q.push(node->right); } } result.push_back(level); } return result; } };

 本小白华中科技大学在读研究生，自然语言处理方向。现每日一更LeetCode  Top 100 Liked Questions, 旨在于通过通俗易懂的画风和诸位计算机朋友们一起成长呀，不局限某题，争取举一反三，所有Questions均呈上C++和Java解法，不足之处多多指正，共同学习。