LeetCode question :
102. Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level)
Definition for a binary tree node
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
Recursive Solution
class Solution {
public:
void visit(TreeNode* root, vector<vector<int>>& ret, int level) {
if (!root) return;
while (ret.size() < level + 1) {
vector<int> v;
ret.push_back(v);
}
ret[level].push_back(root->val);
visit(root->left, ret, level + 1);
visit(root->right, ret, level + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> tree;
visit(root, tree, 0);
return tree;
}
};
Using Queue
class Solution_non_recursive {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> retVec;
if (!root)
return retVec;
queue<TreeNode*> q;
q.push(root);
int i, size;
TreeNode* tN;
while (!q.empty())
{
vector<int> tv;
size = q.size();
for (i = 0; i < size; ++i)
{
tN = q.front();
q.pop();
tv.push_back(tN->val);
if (tN->left) q.push(tN->left);
if (tN->right) q.push(tN->right);
}
retVec.push_back(tv);
}
return retVec;
}
};
Leetcode Question:
104. Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Recursive Solution:
class Solution_recursive {
public:
int getmax(TreeNode* root, int cur){
if(!root) return cur;
return max(getmax(root->left,cur+1),getmax(root->right,cur+1));
}
int maxDepth(TreeNode* root) {
if(!root) return 0;
return getmax(root,1) -1 ;
}
};
Using queue
class Solution_queue {
public:
int maxDepth(TreeNode* root) {
int depth = 0;
if(!root) return depth;
queue<TreeNode*> mq;
mq.push(root);
int size,i;
TreeNode* tn;
while(!mq.empty()){
size = mq.size();
depth++;
for(i = 0; i<size;i++){
tn = mq.front();
mq.pop();
if(tn->left) mq.push(tn->left);
if(tn->right) mq.push(tn->right);
}
}
return depth;
}
};
Top comments (0)