-
Notifications
You must be signed in to change notification settings - Fork 213
/
BinaryTreeZigzagLevelOrderTraversal.h
153 lines (147 loc) · 4.21 KB
/
BinaryTreeZigzagLevelOrderTraversal.h
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
/*
Author: Annie Kim, [email protected]
Date: May 16, 2013
Update: Sep 12, 2013
Problem: Binary Tree Zigzag Level Order Traversal
Difficulty: Easy
Source: https://leetcode.com/onlinejudge#question_103
Notes:
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left
to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
Solution: 1. Queue + reverse.
2. Two stacks.
3. Vector. Contributed by yinlinglin.
*/
/**
* 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>> zigzagLevelOrder(TreeNode *root) {
return zigzagLevelOrder_1(root);
}
// solution 1: Queue + Reverse.
vector<vector<int>> zigzagLevelOrder_1(TreeNode *root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode *> q;
q.push(root);
q.push(NULL); // end indicator of one level
bool left2right = true;
vector<int> level;
while (true)
{
TreeNode *node = q.front(); q.pop();
if (node)
{
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
else
{
if (!left2right)
reverse(level.begin(), level.end());
res.push_back(level);
level.clear();
if (q.empty()) break;
q.push(NULL);
left2right = !left2right;
}
}
return res;
}
// Solution 2: Two stacks.
vector<vector<int>> zigzagLevelOrder_2(TreeNode *root) {
vector<vector<int>> res;
if (!root) return res;
stack<TreeNode *> stk[2];
bool left2right = true;
int cur = 1, last = 0;
stk[last].push(root);
vector<int> level;
while (!stk[last].empty())
{
TreeNode *node = stk[last].top();
stk[last].pop();
if (node)
{
level.push_back(node->val);
if (left2right)
{
stk[cur].push(node->left);
stk[cur].push(node->right);
}
else
{
stk[cur].push(node->right);
stk[cur].push(node->left);
}
}
if (stk[last].empty())
{
if (!level.empty())
res.push_back(level);
level.clear();
swap(cur, last);
left2right = !left2right;
}
}
return res;
}
// Solution 3: Vector. Contributed by yinlinglin.
// Compared to solution 1&2, this solution costs a little more space.
// This solution uses only one single vector instead of two stacks in solution 2.
vector<vector<int>> zigzagLevelOrder_3(TreeNode *root) {
vector<vector<int>> result;
if(!root) return result;
vector<TreeNode*> v;
v.push_back(root);
bool left2right = true;
int begin = 0, end = 0;
while(begin <= end)
{
vector<int> row;
for (int i = end; i >= begin; --i)
{
if (!v[i]) continue;
row.push_back(v[i]->val);
if(left2right)
{
v.push_back(v[i]->left);
v.push_back(v[i]->right);
}
else
{
v.push_back(v[i]->right);
v.push_back(v[i]->left);
}
}
if (!row.empty())
result.push_back(row);
begin = end + 1;
end = v.size() - 1;
left2right = !left2right;
}
return result;
}
};