daily leetcode - binary-tree-zigzag-level-order-traversal - !
题目地址
https://leetcode.com/problems/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]
,
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
思路
这道二叉树的之字形层序遍历是之前那道 Binary Tree Level Order Traversal 的变形,不同之处在于一行是从左到右遍历,下一行是从右往左遍历,交叉往返的之字形的层序遍历。最简单直接的方法就是利用层序遍历,并使用一个变量 cnt 来统计当前的层数(从0开始),将所有的奇数层的结点值进行翻转一下即可,参见代码如下:
解法一:
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> res;
queue<TreeNode*> q{{root}};
int cnt = 0;
while (!q.empty()) {
vector<int> oneLevel;
for (int i = q.size(); i > 0; --i) {
TreeNode *t = q.front(); q.pop();
oneLevel.push_back(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
if (cnt % 2 == 1) reverse(oneLevel.begin(), oneLevel.end());
res.push_back(oneLevel);
++cnt;
}
return res;
}
};
我们可以将上面的解法进行优化一下,翻转数组虽然可行,但是比较耗时,假如能够直接计算出每个结点值在数组中的坐标,就可以直接进行更新了。由于每层的结点数是知道的,就是队列的元素个数,所以可以直接初始化数组的大小。此时使用一个变量 leftToRight 来标记顺序,初始时是 true,当此变量为 true 的时候,每次加入数组的位置就是i本身,若变量为 false 了,则加入到 size-1-i 位置上,这样就直接相当于翻转了数组。每层遍历完了之后,需要翻转 leftToRight 变量,同时不要忘了将 oneLevel 加入结果 res,参见代码如下:
解法二:
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> res;
queue<TreeNode*> q{{root}};
bool leftToRight = true;
while (!q.empty()) {
int size = q.size();
vector<int> oneLevel(size);
for (int i = 0; i < size; ++i) {
TreeNode *t = q.front(); q.pop();
int idx = leftToRight ? i : (size - 1 - i);
oneLevel[idx] = t->val;
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
leftToRight = !leftToRight;
res.push_back(oneLevel);
}
return res;
}
};
我们也可以使用递归的方法来解,这里实际上用的是先序遍历,递归函数需要一个变量 level 来记录当前的深度,由于 level 是从0开始的,假如结果 res 的大小等于 level,就需要在结果 res 中新加一个空集,这样可以保证 res[level] 不会越界。取出 res[level] 之后,判断 levle 的奇偶,若其为偶数,则将 node->val 加入 oneLevel 的末尾,若为奇数,则加在 oneLevel 的开头。然后分别对 node 的左右子结点调用递归函数,此时要传入 level+1 即可,参见代码如下:
解法三:
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
helper(root, 0, res);
return res;
}
void helper(TreeNode* node, int level, vector<vector<int>>& res) {
if (!node) return;
if (res.size() <= level) {
res.push_back({});
}
vector<int> &oneLevel = res[level];
if (level % 2 == 0) oneLevel.push_back(node->val);
else oneLevel.insert(oneLevel.begin(), node->val);
helper(node->left, level + 1, res);
helper(node->right, level + 1, res);
}
};
思路2
这道题可以借助队列
实现,首先把root入队,然后入队一个特殊元素Null(来表示每层的结束)。
然后就是while(queue.length), 每次处理一个节点,都将其子节点(在这里是left和right)放到队列中。
然后不断的出队, 如果出队的是null,则表式这一层已经结束了,我们就继续push一个null。
关键点解析
-
队列
-
队列中用Null(一个特殊元素)来划分每层
-
树的基本操作- 遍历 - 层次遍历(BFS)
代码
- 语言支持:JS,C++
JavaScript Code:
/*
* @lc app=leetcode id=103 lang=javascript
*
* [103] Binary Tree Zigzag Level Order Traversal
*
* https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/
*
* algorithms
* Medium (40.57%)
* Total Accepted: 201.2K
* Total Submissions: 493.7K
* Testcase Example: '[3,9,20,null,null,15,7]'
*
* 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]
* ]
*
*
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var zigzagLevelOrder = function(root) {
if (!root) return [];
const items = [];
let isOdd = true;
let levelNodes = [];
const queue = [root, null];
while(queue.length > 0) {
const t = queue.shift();
if (t) {
levelNodes.push(t.val)
if (t.left) {
queue.push(t.left)
}
if (t.right) {
queue.push(t.right)
}
} else {
if (!isOdd) {
levelNodes = levelNodes.reverse();
}
items.push(levelNodes)
levelNodes = [];
isOdd = !isOdd;
if (queue.length > 0) {
queue.push(null);
}
}
}
return items
};
C++ Code:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
auto ret = vector<vector<int>>();
if (root == nullptr) return ret;
auto queue = vector<const TreeNode*>{root};
auto isOdd = true;
while (!queue.empty()) {
auto sz = queue.size();
auto level = vector<int>();
for (auto i = 0; i < sz; ++i) {
auto n = queue.front();
queue.erase(queue.begin());
if (isOdd) level.push_back(n->val);
else level.insert(level.begin(), n->val);
if (n->left != nullptr) queue.push_back(n->left);
if (n->right != nullptr) queue.push_back(n->right);
}
isOdd = !isOdd;
ret.push_back(level);
}
return ret;
}
};
拓展
由于二叉树是递归结构,因此,可以采用递归的方式来处理。在递归时需要保留当前的层次信息(从0开始),作为参数传递给下一次递归调用。
描述
- 当前层次为偶数时,将当前节点放到当前层的结果数组尾部
- 当前层次为奇数时,将当前节点放到当前层的结果数组头部
- 递归对左子树进行之字形遍历,层数参数为当前层数+1
- 递归对右子树进行之字形遍历,层数参数为当前层数+1
C++实现
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
auto ret = vector<vector<int>>();
zigzagLevelOrder(root, 0, ret);
return ret;
}
private:
void zigzagLevelOrder(const TreeNode* root, int level, vector<vector<int>>& ret) {
if (root == nullptr || level < 0) return;
if (ret.size() <= level) {
ret.push_back(vector<int>());
}
if (level % 2 == 0) ret[level].push_back(root->val);
else ret[level].insert(ret[level].begin(), root->val);
zigzagLevelOrder(root->left, level + 1, ret);
zigzagLevelOrder(root->right, level + 1, ret);
}
};
本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode