AlgoPressAppearance
32-III-从上到下打印二叉树III
题目描述
https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如: 给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
提示：
节点总数 <= 1000
思路1 依次放入，根据方向逐次展开
基本思路
- 使用 Queue 逐次展开 root
- 从 Queue 里面每一行输出展开的时候，根据方向决定是否先放入栈，使用 leftToRight 布尔表示方向
实现代码
csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
// 基本思路
// 1. 使用 Queue 逐次展开 root
// 2. 从 Queue 里面每一行输出展开的时候，根据方向决定是否先放入栈，使用 leftToRight 布尔表示方向
public IList<IList<int>> LevelOrder1(TreeNode root) {
IList<IList<int>> arr = new List<IList<int>>();
Queue<TreeNode> myQueue = new Queue<TreeNode>();
bool leftToRight = true;
if(root != null){
//先放入初始节点
myQueue.Enqueue(root);
while(myQueue.Count > 0 ){
Console.WriteLine("Expanding {0}",myQueue.Count);
int count = myQueue.Count;
List<int> row = new List<int>();
Stack<int> stack = new Stack<int>();
for(int i = 0; i < count; i++){
TreeNode node = myQueue.Dequeue();
if(leftToRight){
row.Add(node.val);
}
else{
stack.Push(node.val);
}
//展开子节点
if(node.left != null){
myQueue.Enqueue(node.left);
}
if(node.right != null){
myQueue.Enqueue(node.right);
}
}
//将数据放入数组，如果是倒序的，则先从 stack 里面取出来
if(!leftToRight){
while(stack.Count > 0){
row.Add(stack.Pop());
}
}
arr.Add(row);
//设置下一次的方向
leftToRight = !leftToRight;
}
}
return arr;
}
public IList<IList<int>> LevelOrder(TreeNode root) {
return LevelOrder1(root);
}
}
思路2 ：不使用栈，直接根据方向 从左到右 加入 Queue 或反向加入 【TODO】
实现代码
csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
// 3. 新的思路，不使用栈，直接根据方向 从左到右 加入 Queue，或者从右到左 加入 Queue
// 测试数据： [1,2,3,4,null,null,5] 结果不正确，奇怪
public IList<IList<int>> LevelOrder2(TreeNode root) {
IList<IList<int>> arr = new List<IList<int>>();
Queue<TreeNode> myQueue = new Queue<TreeNode>();
bool leftToRight = true;
if(root != null){
//先放入初始节点
myQueue.Enqueue(root);
while(myQueue.Count > 0 ){
//设置下一次的方向:因为第一个Enqueue的是从左到右，所以这里就变成从右到左
Console.WriteLine("Expanding {0}",myQueue.Count);
leftToRight = !leftToRight;
int count = myQueue.Count;
List<int> row = new List<int>();
for(int i = 0; i < count; i++){
TreeNode node = myQueue.Dequeue();
row.Add(node.val);
if(leftToRight){
//从左往右展开子节点
if(node.left != null){
myQueue.Enqueue(node.left);
}
if(node.right != null){
myQueue.Enqueue(node.right);
}
}
else{
//从右往左展开子节点
if(node.right != null){
myQueue.Enqueue(node.right);
}
if(node.left != null){
myQueue.Enqueue(node.left);
}
}
}
arr.Add(row);
}
}
return arr;
}
public IList<IList<int>> LevelOrder(TreeNode root) {
return LevelOrder2(root);
}
}