58 按之字形顺序打印二叉树

题目描述

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

代码一

思想:利用两个栈来分别存取交替层,每一层的遍历方向交替改变,每个栈只存放一层的节点,只有遍历完该栈后才存放对应交替层的节点

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
        if(pRoot==null)return arr;
        boolean flag = true;//因为每一层遍历方向都是交替的所以设置标注位
        Stack<TreeNode> s1 = new Stack<TreeNode>();//交替层
        s1.push(pRoot);
        Stack<TreeNode> s2 = new Stack<TreeNode>();//交替层    
        while(!s1.isEmpty()||!s2.isEmpty()) {
            if(flag) {
                ArrayList<Integer> arrRow = new ArrayList<Integer>();
                while(!s1.isEmpty()) {
                    TreeNode node = s1.pop();
                    arrRow.add(node.val);
                    if(node.left!=null)s2.push(node.left);
                    if(node.right!=null)s2.push(node.right);
                }
                if(!arrRow.isEmpty()) {
                    arr.add(arrRow);
                    flag=false;
                }
            }else {
                ArrayList<Integer> arrRow = new ArrayList<Integer>();
                while(!s2.isEmpty()) {
                    TreeNode node = s2.pop();
                    arrRow.add(node.val);
                    if(node.right!=null)s1.push(node.right);
                    if(node.left!=null)s1.push(node.left);
                }
                if(!arrRow.isEmpty()) {
                    arr.add(arrRow);
                    flag=true;
                }
            }
        }        
        return arr;

代码二

思想:该方法相对于代码一的精髓是在list.add(0, node.val);,它很好的处理了在每一层遍历方向的问题,而代码的遍历方向的处理是通过对节点加入栈的来改变方向,代码二是通过插入list来改变方向

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
        if(pRoot==null)return arr;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(pRoot);
        boolean flag=true;
        while(!q.isEmpty()) {
            int size = q.size();
            ArrayList<Integer> list = new ArrayList<Integer>();
            for(int i=0;i<size;i++) {
                TreeNode node = q.poll();
                if(node==null)continue;
                if(flag) {
                    list.add(node.val);
                }else {
                    list.add(0, node.val);
                }
                q.add(node.left);
                q.add(node.right);
            }
            if(!list.isEmpty()) {
                arr.add(list);
                flag = !flag;
            }
        }    
        return arr;
    }