문제 URL : https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
Binary Tree Zigzag Level Order Traversal - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제 접근법 :
지그재그 탐색한순서를 리턴하는건데
기본적인 핵심은 bfs를 이용해야합니다.
bfs로 탐색한후 각 높이마다 각 노드들을 순서대로 저장할수있고
bfs로 탐색한것을 한번은 0~사이즈-1만큼을 다음번엔 사이즈-1 에서 0까지를 이렇게 마지막 높이까지
탐색하여 반환하면 되는 문제입니다.
소스코드 :
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
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) {}
};
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> v = bfs(root);
vector<vector<int>> res;
int flag = 1;
for (int i = 0; i < v.size(); i++) {
vector<int> v2;
for (int j = flag==1?0:v[i].size()-1; j < v[i].size()&&j>=0;j+=flag) {
v2.push_back(v[i][j]);
}
flag *= -1;
if(!v2.empty())
res.push_back(v2);
}
return res;
}
vector<vector<int>> bfs(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> q;
if (root)
q.push(root);
while (!q.empty()) {
int qsize = q.size();
vector<int> v;
while (qsize--) {
TreeNode* cur = q.front();
q.pop();
if (cur == NULL) continue;
v.push_back(cur->val);
q.push(cur->left);
q.push(cur->right);
}
res.push_back(v);
}
return res;
}
};
|
cs |
궁금한점 혹은 모르는점 어떤질문이라도 댓글은 언제나 환영입니다.
'LeetCode' 카테고리의 다른 글
| LeetCode 112 Path Sum (0) | 2021.11.14 |
|---|---|
| LeetCode 257 Binary Tree Paths (0) | 2021.11.14 |
| LeetCode 686. Repeated String Match (0) | 2021.07.31 |
| LeetCode 572. Subtree of Another Tree (0) | 2021.07.31 |
| LeetCode 459 Repeated Substring Pattern (0) | 2021.07.31 |
