第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0103. 二叉树的锯齿形层次遍历
题目地址(103. 二叉树的锯齿形层次遍历)
题目描述
和leetcode 102 基本是一样的，思路是完全一样的。
1
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
2
3
例如：
4
给定二叉树 [3,9,20,null,null,15,7],
5
6
3
7
/ \
8
9 20
9
/ \
10
15 7
11
返回锯齿形层次遍历如下：
12
13
[
14
[3],
15
[20,9],
16
[15,7]
17
]
Copied!
前置知识
- 队列
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
这道题可以借助
队列实现，首先把root入队，然后入队一个特殊元素Null(来表示每层的结束)。然后就是while(queue.length), 每次处理一个节点，都将其子节点（在这里是left和right）放到队列中。
然后不断的出队， 如果出队的是null，则表式这一层已经结束了，我们就继续push一个null。
关键点解析
- 队列
- 队列中用Null(一个特殊元素)来划分每层
- 树的基本操作- 遍历 - 层次遍历（BFS）
代码
- 语言支持：JS，C++
JavaScript Code：
1
/**
2
* @param {TreeNode} root
3
* @return {number[][]}
4
*/
5
var zigzagLevelOrder = function(root) {
6
if (!root) return [];
7
const items = [];
8
let isOdd = true;
9
let levelNodes = [];
10
11
const queue = [root, null];
12
13
14
while(queue.length > 0) {
15
const t = queue.shift();
16
17
if (t) {
18
levelNodes.push(t.val)
19
if (t.left) {
20
queue.push(t.left)
21
}
22
if (t.right) {
23
queue.push(t.right)
24
}
25
} else {
26
if (!isOdd) {
27
levelNodes = levelNodes.reverse();
28
}
29
items.push(levelNodes)
30
levelNodes = [];
31
isOdd = !isOdd;
32
if (queue.length > 0) {
33
queue.push(null);
34
}
35
}
36
}
37
38
return items
39
40
};
Copied!
C++ Code：
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
public:
12
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
13
auto ret = vector<vector<int>>();
14
if (root == nullptr) return ret;
15
auto queue = vector<const TreeNode*>{root};
16
auto isOdd = true;
17
while (!queue.empty()) {
18
auto sz = queue.size();
19
auto level = vector<int>();
20
for (auto i = 0; i < sz; ++i) {
21
auto n = queue.front();
22
queue.erase(queue.begin());
23
if (isOdd) level.push_back(n->val);
24
else level.insert(level.begin(), n->val);
25
if (n->left != nullptr) queue.push_back(n->left);
26
if (n->right != nullptr) queue.push_back(n->right);
27
}
28
isOdd = !isOdd;
29
ret.push_back(level);
30
}
31
return ret;
32
}
33
};
Copied!
拓展
由于二叉树是递归结构，因此，可以采用递归的方式来处理。在递归时需要保留当前的层次信息（从0开始），作为参数传递给下一次递归调用。
描述
- 1.当前层次为偶数时，将当前节点放到当前层的结果数组尾部
- 2.当前层次为奇数时，将当前节点放到当前层的结果数组头部
- 3.递归对左子树进行之字形遍历，层数参数为当前层数+1
- 4.递归对右子树进行之字形遍历，层数参数为当前层数+1
C++实现
1
class Solution {
2
public:
3
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
4
auto ret = vector<vector<int>>();
5
zigzagLevelOrder(root, 0, ret);
6
return ret;
7
}
8
private:
9
void zigzagLevelOrder(const TreeNode* root, int level, vector<vector<int>>& ret) {
10
if (root == nullptr || level < 0) return;
11
if (ret.size() <= level) {
12
ret.push_back(vector<int>());
13
}
14
if (level % 2 == 0) ret[level].push_back(root->val);
15
else ret[level].insert(ret[level].begin(), root->val);
16
zigzagLevelOrder(root->left, level + 1, ret);
17
zigzagLevelOrder(root->right, level + 1, ret);
18
}
19
};
Copied!
相关题目
最近更新 1yr ago