剑指offer66之按之字形顺序打印二叉树（java）

柔情只为你懂 2021-10-18 17:26 198阅读 0赞

**题目描述**  
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

**解题思路**  
设两个栈，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);//入栈，s2奇数层
            
            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;
        }
    
    }