力扣练习——45 二叉树的锯齿形层次遍历

3
1

 /  \
1

int val;

TreeNode *left;

TreeNode *right;

TreeNode() : val(0), left(NULL), right(NULL) {}

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
1
2
3
4
5
6
7
8
9
10
11

int n,count=0;

char item[100];

cin>>n;

if (n==0)

    return NULL;

cin>>item;

TreeNode* root = new TreeNode(atoi(item));

count++;

queue nodeQueue;

nodeQueue.push(root);

while (count>item;

    count++;

    if (strcmp(item,"null")!=0)

    {

        int leftNumber = atoi(item);

        node->left = new TreeNode(leftNumber);

        nodeQueue.push(node->left);

    }

    if (count==n)

        break;

    cin>>item;

    count++;

    if (strcmp(item,"null")!=0)

    {

        int rightNumber = atoi(item);

        node->right = new TreeNode(rightNumber);

        nodeQueue.push(node->right);

    }

}

return root;
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

TreeNode* root;

root=inputTree();

vector > res=Solution().zigzagLevelOrder(root);

for(int i=0; i v=res[i];

    for(int j=0; j

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17

}
2.输入说明
首先输入结点的数目n（注意，这里的结点包括题中的null空结点）

然后输入n个结点的数据，需要填充为空的结点，输入null。
3.输出说明
输出结果，每个数据的后面跟一个空格。
4.范例
输入
7
3 9 20 null null 15 7
输出
3 20 9 15 7
5.代码

#include 
#include 
#include 
#include 

using namespace std;


struct TreeNode

{

	int val;

	TreeNode *left;

	TreeNode *right;

	TreeNode() : val(0), left(NULL), right(NULL) {}

	TreeNode(int x) : val(x), left(NULL), right(NULL) {}

	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

TreeNode* inputTree()

{

	int n, count = 0;

	char item[100];

	cin >> n;

	if (n == 0)

		return NULL;

	cin >> item;

	TreeNode* root = new TreeNode(atoi(item));

	count++;

	queue<TreeNode*> nodeQueue;

	nodeQueue.push(root);

	while (count < n)

	{

		TreeNode* node = nodeQueue.front();

		nodeQueue.pop();

		cin >> item;

		count++;

		if (strcmp(item, "null") != 0)

		{

			int leftNumber = atoi(item);

			node->left = new TreeNode(leftNumber);

			nodeQueue.push(node->left);

		}

		if (count == n)

			break;

		cin >> item;

		count++;

		if (strcmp(item, "null") != 0)

		{

			int rightNumber = atoi(item);

			node->right = new TreeNode(rightNumber);

			nodeQueue.push(node->right);

		}

	}

	return root;

}

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {

	//思想：要求从左到右，下一层从右往左遍历
	//用双端队列，若从左往右，则队尾插入结点，若从右往左，从在队头插入结点   用flag记录遍历方向 ，flag=1从左往后 ，flag=0从右往左

    vector<vector<int> >res;
    
	if (!root)
		return res; //空树
	
	queue<TreeNode*>q_node;//记录每个结点
	q_node.push(root);//根节点入队列
	int flag = 1;//记录遍历方向，若从左往右，则为1

	while (!q_node.empty())
	{
		//使用双端队列记录每层结点
		deque<int> LevelList;
		int size = q_node.size();
		for (int i = 0; i < size; i++)
		{
			auto node = q_node.front();//访问每一个结点
			q_node.pop();//结点出队
			
			if (flag == 1)//正向【从左向右】遍历，在队尾插入元素
			{
				LevelList.push_back(node->val);//队尾插入
			}
			else
			{
				LevelList.push_front(node->val);//队头插入
			}

			//该结点左子树存在，左子树入队列
			if (node->left)
				q_node.push(node->left);//结点入队
			if (node->right)
				q_node.push(node->right);
		}
		flag=!flag;//这里必须这么写，不能写flag=0;[否则后面一直都是0]
		res.push_back(vector<int>{LevelList.begin(), LevelList.end()});
	}
	return res;
}

int main()

{

	TreeNode* root;

	root = inputTree();

	vector<vector<int> > res = zigzagLevelOrder(root);

	for (int i = 0; i < res.size(); i++)

	{

		vector<int> v = res[i];

		for (int j = 0; j < v.size(); j++)

			cout << v[j] << " ";

	}

}
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168