102. Binary Tree Level Order Traversal 面试题32 - II. 从上到下打印二叉树 II(Leetcode每日一题-2020.05.13)

本文主要是介绍102. Binary Tree Level Order Traversal 面试题32 - II. 从上到下打印二叉树 II(Leetcode每日一题-2020.05.13)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

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

Example

Given binary tree [3,9,20,null,null,15,7],
在这里插入图片描述
return its level order traversal as:

Solution

利用队列进行层序遍历。
注意如何界定一层已经遍历完成。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ret;if(!root)return ret;queue<TreeNode *> my_queue;my_queue.push(root);TreeNode * levelEnd = root;vector<int> level;while(!my_queue.empty()){TreeNode* cur= my_queue.front();my_queue.pop();level.push_back(cur->val);if(cur->left)my_queue.push(cur->left);if(cur->right)my_queue.push(cur->right);if(cur == levelEnd){ret.push_back(level);level.clear();levelEnd = my_queue.back();}}return ret;}
};

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ret;if(!root)return ret;queue<TreeNode*> tn_queue;tn_queue.push(root);while(!tn_queue.empty()){int level_size = tn_queue.size();vector<int> level_vals;for(int i = 0;i<level_size;++i){TreeNode *cur = tn_queue.front();tn_queue.pop();if(cur->left)tn_queue.push(cur->left);if(cur->right)tn_queue.push(cur->right);level_vals.push_back(cur->val);}ret.push_back(level_vals);}return ret;}
};