Binary Tree Level Order Traversal
OJ: https://oj.leetcode.com/problems/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]
]
思想： 若递归，传入层号。若迭代，使用队列，在每层结束时，加入一个标记。
方法一：递归：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
void levelPath(TreeNode* root, int level, vector<vector<int> > &path) {
if(root == NULL) return;
level < path.size() ? path[level].push_back(root->val) : path.push_back(vector<int>(1, root->val));
levelPath(root->left, level+1, path);
levelPath(root->right, level+1, path);
}
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > path;
levelPath(root, 0, path);
return path;
}
};
方法二：迭代
/**
* 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) {
vector<vector<int> > vec;
if(root == NULL) return vec;
queue<TreeNode*> qu;
qu.push(root);
qu.push(0);
vector<int> vec2;
while(!qu.empty()) {
TreeNode *p = qu.front();
qu.pop();
if(!p) {
if(vec2.size()) { vec.push_back(vec2); vec2.clear();}
if(!qu.empty()) qu.push(0);
}else {
vec2.push_back(p->val);
if(p->left) qu.push(p->left);
if(p->right) qu.push(p->right);
}
}
return vec;
}
};
Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example: Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
思想： 目前用两种方法：1 同上，最后将结果反转一下。 2.先求出最大层数，再层序遍历。（也许还有更好的方法）
1.
void levelPath(TreeNode* root, int level, vector<vector<int> > &path) {
if(root == NULL) return;
level < path.size() ? path[level].push_back(root->val) : path.push_back(vector<int>(1, root->val));
levelPath(root->left, level+1, path);
levelPath(root->right, level+1, path);
}
class Solution {
public:
vector<vector<int> > levelOrderBottom(TreeNode *root) {
vector<vector<int> > path;
levelPath(root, 0, path);
return vector<vector<int> > (path.rbegin(), path.rend());
}
};
2.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
int getLevel(TreeNode *root) {
if(root == NULL) return -1;
return max(getLevel(root->left), getLevel(root->right)) + 1;
}
void getLevel2(TreeNode *root, int curL, vector<vector<int> > &vec) {
if(root == NULL) return;
vec[curL].push_back(root->val);
getLevelBottom(root->left, curL-1, vec);
getLevelBottom(root->right,curL-1, vec);
}
class Solution {
public:
vector<vector<int> > levelOrderBottom(TreeNode *root) {
int L = getLevel(root);
vector<vector<int> > vec(L+1, vector<int>());
getLevelBottom(root, L, vec);
return vec;
}
};