Code & Fun

第97天。

今天的题目是Binary Tree Zigzag Level Order Traversal:

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],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

return its zigzag level order traversal as:

1
2
3
4
5
[
[3],
[20,9],
[15,7]
]

首先想到的是用层次遍历的方式来实现。

简单的层次遍历:

1
2
3
4
5
6
7
8
9
10
11
void levelTra(TreeNode *root) {
if (root == nullptr) return ;
queue<TreeNode *> q;
q.push(root);
while(!q.empty()) {
root = q.top(); q.pop();
cout << root->val;
if (root->left) q.push(root->left);
if (root->right) q.push(root->right);
}
}

但是上面的方法是没法区分层数的,我们通过nullptr来表示换行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void levelTra(TreeNode *root) {
if (root == nullptr) return ;
queue<TreeNode *> q;
q.push(root);
q.push(nullptr);
while(true) {
root = q.top(); q.pop();

if (root == nullptr) {
cout << "new level" << endl;
if (q.empty()) break;
q.push(nullptr);
}

cout << root->val;
if (root->left) q.push(root->left);
if (root->right) q.push(root->right);
}
}
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
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int> > ret;
vector<int> tmp;
if (root == nullptr) return ret;
//level tra

bool flag = true; //判断遍历方向

queue<TreeNode *> q;
q.push(root);
q.push(nullptr);

while(true) {
root = q.front(); q.pop();
if (root == nullptr) {

if (flag) ret.push_back(tmp);
else ret.push_back(vector<int>(tmp.rbegin(), tmp.rend()));

tmp.clear();
flag = !flag;

if (q.empty()) break;
q.push(nullptr);
continue;
}


tmp.push_back(root->val);
if (root->left) q.push(root->left);
if (root->right) q.push(root->right);
}

return ret;
}

然后是dicuss中的方法,简单的来说就是通过深度优先遍历来生成获取层次遍历的每层的数组(好像之前写过?),然后就会比前面用queue的方法快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void travel(TreeNode *root, vector<vector<int> > &ret, int level) {
if (root == nullptr) return ;
if (level >= ret.size()) ret.push_back(vector<int>());

ret[level].push_back(root->val);

travel(root->left, ret, level + 1);
travel(root->right, ret, level + 1);
}

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int>> ret;
travel(root, ret, 0);

for(int i = 0;i < ret.size();i++) {
if (i % 2) reverse(ret[i].begin(), ret[i].end());
}

return ret;
}

本文首发于Code & Fun