Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
3
/ \
9 20
/ \
15 7
should return its level order traversal as:
[ [3], [9,20], [15,7] ]
Iterative DFS
DFS (Depth First Search) visits the nodes as deep as possible (front left to right nodes). If we record the current level, and should be able to push the node value to its corresponding level vector.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | /** * 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>> r; if (root == NULL) { return r; } stack<pair<TreeNode*, int>> st; auto p = root; int level = 0; while (p || !st.empty()) { if (p) { if (level + 1 > r.size()) { r.resize(level + 1); } r[level].push_back(p->val); st.push(make_pair(p, level++)); p = p->left; } else { auto x = st.top(); p = x.first; level = x.second + 1; st.pop(); p = p->right; } } return r; } }; |
/**
* 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>> r;
if (root == NULL) {
return r;
}
stack<pair<TreeNode*, int>> st;
auto p = root;
int level = 0;
while (p || !st.empty()) {
if (p) {
if (level + 1 > r.size()) {
r.resize(level + 1);
}
r[level].push_back(p->val);
st.push(make_pair(p, level++));
p = p->left;
} else {
auto x = st.top();
p = x.first;
level = x.second + 1;
st.pop();
p = p->right;
}
}
return r;
}
};This emulate the recursion using the stack data structure. When new left nodes are pushed to the stack, the level is also recorded.
Iterative BFS
Breadth First Search (BFS) implements a level-by-level traversal. We initialize the queue by the Root node and level 0, level-by-level pushing the nodes. When dealing a node, we push its value to its corresponding level vector.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> r; if (root == NULL) { return r; } queue<pair<TreeNode*, int>> q; q.push(make_pair(root, 0)); while (!q.empty()) { auto p = q.front(); q.pop(); if (p.second >= r.size()) { r.push_back(vector<int>()); } r[p.second].push_back(p.first->val); if (p.first->left != NULL) { q.push(make_pair(p.first->left, p.second + 1)); } if (p.first->right != NULL) { q.push(make_pair(p.first->right, p.second + 1)); } } return r; } }; |
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> r;
if (root == NULL) {
return r;
}
queue<pair<TreeNode*, int>> q;
q.push(make_pair(root, 0));
while (!q.empty()) {
auto p = q.front();
q.pop();
if (p.second >= r.size()) {
r.push_back(vector<int>());
}
r[p.second].push_back(p.first->val);
if (p.first->left != NULL) {
q.push(make_pair(p.first->left, p.second + 1));
}
if (p.first->right != NULL) {
q.push(make_pair(p.first->right, p.second + 1));
}
}
return r;
}
};Related Puzzles
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
https://leetcode.com/problems/binary-tree-level-order-traversal/
These two puzzles can in fact be solved by using the same approach. The only difference is that it asks for a reverse level order, which can simply be reversed using:
1 | reverse(r.begin(), r.end()); |
reverse(r.begin(), r.end());
See also: Binary Tree Level Order Traversal Algorithm in Go
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Dynamic Programming - Perfect Squares
Next Post: The Permutation Algorithm for Arrays using Recursion
