题目描述: 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
题目描述:
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
解题思路:
//1.使用两个栈来分别存储奇数层节点和偶数层节点。 //2.注意两个栈的插入顺序是不同的。 //3.对于奇数层来说，也就是从左往右的顺序，先添加左子树，然后添加右子树。对于偶数层，刚好相反，先添加右子树，然后添加左子树。
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
//利用两个栈的辅助空间分别存储奇数偶数层的节点，然后打印输出。或使用链表的辅助空间来实现，利用链表的反向迭实现逆序输出。
public ArrayList > Print(TreeNode pRoot) {
ArrayList> res = new ArrayList<>();
if(pRoot == null)
return res;
Stack s1 = new Stack<>();
Stack s2 = new Stack<>();
s1.push(pRoot);
int level = 1;
while (!s1.empty()||!s2.empty()) {
if (level %2 != 0) {
ArrayList list = new ArrayList<>();
while (!s1.empty()) {
TreeNode node = s1.pop();
if (node!= null) {
list.add(node.val);
s2.push(node.left);//因为偶数层，先右后左，所以要先放左子树，栈
s2.push(node.right);
}
}
if (!list.isEmpty()) {
res.add(list);
level++;
}
}
else {
ArrayList list = new ArrayList<>();
while (!s2.empty()) {
TreeNode node = s2.pop();
if (node!= null) {
list.add(node.val);
s1.push(node.right);
s1.push(node.left);
}
}
if (!list.isEmpty()) {
res.add(list);
level++;
}
}
}
return res;
}
}
Original: https://www.cnblogs.com/lkylin/p/13670992.html
Author: 手下留情
Title: 剑指Offer:按之字形顺序打印二叉树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/564821/
转载文章受原作者版权保护。转载请注明原作者出处！