Last active
August 29, 2015 14:03
-
-
Save walkingtospace/6867d9b1c08600f9ccef to your computer and use it in GitHub Desktop.
binary-tree-level-order-traversal
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
https://oj.leetcode.com/problems/binary-tree-level-order-traversal/ | |
/** | |
* Definition for binary tree | |
* struct TreeNode { | |
* int val; | |
* TreeNode *left; | |
* TreeNode *right; | |
* TreeNode(int x) : val(x), left(NULL), right(NULL) {} | |
* }; | |
*/ | |
/* | |
solution | |
1. BFS + 매 iteration마다 marker를 queue에 삽입하여 level 구분하기 | |
2. counter를 이용하여 매 iteration마다 자식노드 갯수 세기 | |
3. in-order로 depth level을 알수있으므로 바로 push(loop로 구현할 경우 in-place로 구현 가능) | |
*/ | |
class Solution { | |
public: | |
vector<vector<int>> levelOrder(TreeNode *root) { | |
vector<vector<int>> res; | |
if(root == NULL) return res; | |
vector<int> level; | |
queue<TreeNode*> input; | |
int cnt = 1; | |
input.push(root); | |
while(!input.empty()) { | |
level.clear(); | |
int levelCnt = 0; | |
for(int i=0 ; i<cnt; i++) { | |
TreeNode* node = input.front(); | |
level.push_back(node->val); | |
input.pop(); | |
if(node->left != NULL) { | |
input.push(node->left); | |
levelCnt++; | |
} | |
if(node->right != NULL) { | |
input.push(node->right); | |
levelCnt++; | |
} | |
} | |
cnt = levelCnt; | |
res.push_back(level); | |
} | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment