Binary Tree Level Order Traversal
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]
]
解法一：递归
参考了Discussion中stellari的做法，递归进行层次遍历，并将每个level对应于相应的vector。
/**
* 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> > result; void levelTra(TreeNode *root, int level)
{
if(root == NULL)
return;
if(level == result.size())
{
vector<int> v;
result.push_back(v);
}
result[level].push_back(root->val);
levelTra(root->left, level+);
levelTra(root->right, level+);
} vector<vector<int> > levelOrder(TreeNode *root)
{
levelTra(root, );
return result;
}
};
解法二：
层次遍历，层数使用level来记录。同层装入同一个vector。
当进入新的一层时，将上层的vector保存，并清空。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/ struct Node
{
TreeNode* tNode;
int level;
Node(TreeNode* newtNode, int newlevel): tNode(newtNode), level(newlevel) {}
}; class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > ret;
if(!root)
return ret;
// push root
Node* rootNode = new Node(root, );
queue<Node*> Nqueue;
Nqueue.push(rootNode); vector<int> cur;
int curlevel = ;
while(!Nqueue.empty())
{
Node* frontNode = Nqueue.front();
Nqueue.pop(); if(frontNode->level > curlevel)
{
ret.push_back(cur);
cur.clear();
curlevel = frontNode->level;
} cur.push_back(frontNode->tNode->val); if(frontNode->tNode->left)
{
Node* leftNode = new Node(frontNode->tNode->left, frontNode->level+);
Nqueue.push(leftNode);
}
if(frontNode->tNode->right)
{
Node* rightNode = new Node(frontNode->tNode->right, frontNode->level+);
Nqueue.push(rightNode);
}
}
ret.push_back(cur);
return ret;
}
};