AlgoPressAppearance
0103-二叉树的锯齿形层序遍历
https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如： 给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下：
[
[3],
[20,9],
[15,7]
]
思路
广度优先搜索，使用Queue保存节点
参考代码
csharp
public class Solution {
public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
List<IList<int>> result = new List<IList<int>>();
Queue<TreeNode> queue = new Queue<TreeNode>();
if(root == null){
return result;
}
queue.Enqueue(root);
bool leftToRight= true;
int count = 0;
while(queue.Count > 0) {
List<int> list = new List<int>();
Stack<int> stack = new Stack<int>();
count = queue.Count;
for(int i=0; i<count; i++){
TreeNode node = queue.Dequeue();
//展开节点
if(node.left != null){
queue.Enqueue(node.left);
}
if(node.right != null){
queue.Enqueue(node.right);
}
//直接输出
if(leftToRight){
list.Add(node.val);
}
else{
stack.Push(node.val);
}
}
while(stack.Count > 0){
list.Add(stack.Pop());
}
leftToRight = !leftToRight;
result.Add(list);
}
return result;
}
}