-
Notifications
You must be signed in to change notification settings - Fork 1
/
ZigZag_Tree_Traversal.cpp
80 lines (65 loc) · 1.34 KB
/
ZigZag_Tree_Traversal.cpp
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
/*
Problem Statement:
-----------------
Given a Binary Tree. Find the Zig-Zag Level Order Traversal of the Binary Tree.
Example 1:
---------
Input:
3
/ \
2 1
Output: 3 1 2
Example 2:
---------
Input:
7
/ \
9 7
/ \ /
8 8 6
/ \
10 9
Output: 7 7 9 8 8 6 9 10
Your Task: You don't need to read input or print anything. Your task is to complete the function zigZagTraversal() which takes
the root node of the Binary Tree as its input and returns a list containing the node values as they appear in the Zig-Zag Level-Order Traversal of the Tree.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
*/
// Link --> https://practice.geeksforgeeks.org/problems/zigzag-tree-traversal/1#
// Code:
vector <int> zigZagTraversal(Node* root)
{
vector <int> res;
stack <Node*> s1 , s2;
s1.push(root);
bool flag = true;
while(!s1.empty())
{
Node* temp = s1.top();
s1.pop();
if(temp)
{
res.push_back(temp->data);
if(flag == true)
{
if(temp->left)
s2.push(temp->left);
if(temp->right)
s2.push(temp->right);
}
else
{
if(temp->right)
s2.push(temp->right);
if(temp->left)
s2.push(temp->left);
}
}
if(s1.empty())
{
flag = !flag;
swap(s1 , s2);
}
}
return res;
}