欢迎访问LeetCode题解合集
题目描述
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:
给定二叉树 [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下:
[
[3],
[20,9],
[15,7]
]
题解:
两种思路:
- 参考 二叉树的层序遍历 ,将偶数行的元素逆序即可
- 使用类似于双端队列结构,奇数行插入首部,偶数行插入尾部
法一:
递归 + 逆序。
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
/**
* 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>> ret;
void dfs( TreeNode *root, int dep ) {
if ( !root ) return;
if ( ret.size() < dep )
ret.emplace_back( vector<int>{} );
ret[dep - 1].emplace_back( root->val );
dfs( root->left, dep + 1 );
dfs( root->right, dep + 1 );
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
dfs( root, 1 );
for ( int i = 0; i < ret.size(); ++i )
if ( i & 1 ) reverse( ret[i].begin(), ret[i].end() );
return ret;
}
};
/*
时间:4ms,击败:64.96%
内存:11.6MB,击败:21.90%
*/
法二:
迭代(广搜) + 逆序。
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
/**
* 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>> ret;
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if ( !root ) return ret;
queue<TreeNode*> q;
q.push( root );
int size, i;
while ( q.size() ) {
size = q.size();
ret.emplace_back( vector<int>{} );
for ( i = 0; i < size; ++i ) {
root = q.front(); q.pop();
ret.back().emplace_back( root->val );
if ( root->left ) q.push( root->left );
if ( root->right ) q.push( root->right );
}
}
for ( int i = 0; i < ret.size(); ++i )
if ( i & 1 ) reverse( ret[i].begin(), ret[i].end() );
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:10.9MB,击败:97.07%
*/
法三:
双端队列。
/**
* 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>> ret;
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if ( !root ) return ret;
deque<TreeNode*> dq;
dq.push_front( root );
bool order = true;
int size, i;
while ( dq.size() ) {
size = dq.size();
ret.emplace_back( vector<int>{} );
for ( i = 0; i < size; ++i ) {
if ( order ) {
root = dq.front(); dq.pop_front();
if ( root->left ) dq.push_back( root->left );
if ( root->right ) dq.push_back( root->right );
} else {
root = dq.back(); dq.pop_back();
if ( root->right ) dq.push_front( root->right );
if ( root->left ) dq.push_front( root->left );
}
ret.back().emplace_back( root->val );
}
order = !order;
}
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:11.1MB,击败:89.89%
*/