Binary Tree Zigzag Level Order Traversal

The more we do,the more we can do.

1. 题目:二叉树锯齿形层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

2. 解析

本来看错题目以为就是简单的层次遍历,一个队列就可以解决问题。后来发现有个 锯齿形(zigzag) 。这样遍历每一层就可能有两个顺序,一个是 从左到右(ltr),另一个是 从右到左(rtl),整个的遍历顺序就是先ltr,再rtl,如此循环交替。

拿上面的例子看一下:

  • 当遍历顺序是rtl时,也就是第二层,我们最终要的顺序应该是 20->9,这里我们先把9插入队列,再插入20,然后每次从队尾取出元素,就是要求的顺序。

  • 当遍历顺序是ltr时,看看第三层,我们最终要的顺序应该是 15->7,这里我们先把7插入队列,再插入15,然后每次从队尾取出元素,就是要求的顺序。

可以比较一下:当 rtl 时,先插入的是左儿子,当 ltr 时,先插入的是右儿子。思路有了,直接写代码。C++ 代码如下:

3. 代码

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
#include <iostream>
#include <vector>

using namespace std;

typedef struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void printResult(vector<vector<int>> res) {
int size = res.size();
for (int i = 0; i < size; ++i) {
vector<int> item = res[i];
for (int j = 0; j < item.size(); ++j) {
cout << item[j] << " ";
}
cout << endl;
}
}

/**
* 1. 生成一个哨兵指针,始终指向某一层的第一个节点
* 2. 每次将节点插入到一个队列末尾,当遍历到上一个哨兵的时候,表面这一层全部遍历结束
* @param root
* @return
*/
vector<vector<int>> zigzagLevelOrder(TreeNode *root) {

vector<vector<int>> result;

vector<vector<TreeNode *>> resultNodes;

bool ltr = false;//true : 从左往右遍历.false : 从右往左遍历

if (root == NULL) {
return result;
}
TreeNode *layerEnd = root;//指向某一层队首的哨兵

vector<TreeNode *> currentNodes;
vector<TreeNode *> nextNodes;

vector<int> next;

currentNodes.push_back(root);

resultNodes.push_back(currentNodes);

while (!currentNodes.empty()) {

//1. 每次都从队尾访问并取出,
TreeNode *tmp;
tmp = currentNodes.back();
currentNodes.pop_back();

//2. 插入到当前层的表示队列 next
cout << tmp->val << endl;
next.push_back(tmp->val);

if (ltr) {
//3. 如果是 ltr
if (tmp->right != NULL) {
nextNodes.push_back(tmp->right);
}

if (tmp->left != NULL) {
nextNodes.push_back(tmp->left);
}
} else {
//3. 如果是 rtl
if (tmp->left != NULL) {
nextNodes.push_back(tmp->left);
}

if (tmp->right != NULL) {
nextNodes.push_back(tmp->right);
}
}

//4. 如果遇到哨兵节点,表面此层遍历结束。
if (tmp == layerEnd) {
//存入结果
result.push_back(next);
resultNodes.push_back(nextNodes);

//注意这里是结束条件
if (nextNodes.empty()) {
break;
}

//哨兵放在队首
layerEnd = nextNodes.front();

//将下一层加入缓存遍历
currentNodes.clear();
currentNodes.insert(currentNodes.end(), nextNodes.begin(), nextNodes.end());

//注意清空
nextNodes.clear();
next.clear();
ltr = !ltr;
}

}
printResult(result);
return result;

}

4. 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main() {
TreeNode *node_a = new TreeNode(3);
TreeNode *node_b = new TreeNode(9);
TreeNode *node_c = new TreeNode(20);
TreeNode *node_d = new TreeNode(15);
TreeNode *node_e = new TreeNode(7);

node_a->left = node_b;
node_a->right = node_c;
node_c->left = node_d;
node_c->right = node_e;

zigzagLevelOrder(node_a);
return 0;
}

输出:

1
2
3
3 
20 9
15 7

正确。


THE END.

评论