Binary Tree Level Order Traversal---LeetCode(二叉树层序遍历)
题目描述:
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,#,#,15,7}
,
3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7]]
confused what "{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1 / \ 2 3 / 4 \ 5The above binary tree is serialized as
"{1,2,3,#,#,4,#,#,5}"
.代码:/** * Definition for binary tree * 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) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<vector<int> > res; vector<int> lev; if(root == NULL) return res; queue<TreeNode *> que; que.push(root); que.push(NULL); //end of one level while(true) { TreeNode *cur = que.front(); que.pop(); if(!cur) { res.push_back(lev); lev.clear(); if(que.empty()) break; que.push(NULL); } else { lev.push_back(cur->val); if(cur->left) que.push(cur->left); if(cur->right) que.push(cur->right); } } return res; }};