请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
设两个栈,s2存放奇数层,s1存放偶数层
遍历s2节点的同时按照左子树、右子树的顺序加入s1,
遍历s1节点的同时按照右子树、左子树的顺序加入s2
import java.util.ArrayList;
import java.util.Stack;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
Stack<TreeNode> s1 = new Stack<TreeNode>();
Stack<TreeNode> s2 = new Stack<TreeNode>();
int flag = 1;
if(pRoot == null)
return res;
s2.push(pRoot);
ArrayList<Integer> temp = new ArrayList<Integer>();
while(!s1.isEmpty() || !s2.isEmpty()){
if(flag % 2 != 0){
while(!s2.isEmpty()){
TreeNode node = s2.pop();
temp.add(node.val);
if(node.left != null){
s1.push(node.left);
}
if(node.right != null){
s1.push(node.right);
}
}
}
if(flag % 2 == 0){
while(!s1.isEmpty()){
TreeNode node = s1.pop();
temp.add(node.val);
if(node.right != null){
s2.push(node.right);
}
if(node.left != null){
s2.push(node.left);
}
}
}
res.add(new ArrayList<Integer>(temp));
temp.clear();
flag ++;
}
return res;
}
}
版权属于: 尾尾部落
原文地址: https://cloud.tencent.com/developer/article/1327745
转载时必须以链接形式注明原始出处及本声明。
window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"1","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')0||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];