博客

题目

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

分析

此题就是层序遍历变形而来。多了两个要求：

1. 记录当前层数；
2. 偶数层要倒序打印。

可以引用两个栈来解决，栈1存储奇数层的节点，栈2存储偶数层的节点。

listAll分层存放所有节点，是ArrayList<ArrayList< Integer >>类型。

1. 如图，首先将根节点A压入stack1，并设置layer=1：
   
   

2. 接下来循环处理stack1和stack2中的节点，前提是至少有一个栈非空，如果layer为奇数，则处理stack1的节点：
   
   当stack1非空时，pop出stack1的节点：
   
   

3. 然后将A添加到list1里面（list1存放奇数层节点的值，是ArrayList< Integer >类型），并将A的孩子
   
   从左到右
   
   push到stack2里面（这样出栈顺序就是倒序了）：
   
   

4. 当stack1为空时，说明当前奇数层已经处理完毕，此时将layer++，并判断list1是否非空，若非空，则将list1加到listAll里面。

5. 继续循环，若layer为偶数时，处理stack2中的节点，当stack2非空时，将stack2中的元素pop出：
   
   

6. 并添加到list2中（list2存放偶数层节点），这样list2的存放顺序就是：C，B

7. 同时将layer++

8. 之后将C和B的孩子按
   
   从右到左
   
   的顺序push到stack1中（这是为了让stack1的出栈顺序是正序）：
   
   
   
   之后再按照第一步的程序去处理stack1中的节点。直到stack1和stack2都为空为止。

代码

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> listAll = new ArrayList<>();
        if(pRoot == null){
            return listAll;
        }
        Stack<TreeNode> s1 = new Stack<>(); //存奇数层节点
        Stack<TreeNode> s2 = new Stack<>(); //存偶数层节点
        s1.push(pRoot);
        int layer = 1; //记录层数
        while(!s1.isEmpty() || !s2.isEmpty()){
            if(layer%2 != 0){ //处理奇数层
                ArrayList<Integer> list1 = new ArrayList<>(); //存放当前奇数层的节点
                while(!s1.isEmpty()){
                    TreeNode node = s1.pop();
                    list1.add(node.val);
                    if(node.left != null){
                        s2.push(node.left);
                    }
                    if(node.right != null){
                        s2.push(node.right);
                    }
                }
                layer++;
                if(!list1.isEmpty()){
                    listAll.add(list1);
                }
            }
            else{  //处理偶数层节点
                ArrayList<Integer> list2 = new ArrayList<>();
                while(!s2.isEmpty()){
                    TreeNode node = s2.pop();
                    list2.add(node.val);
                    if(node.right != null){
                        s1.push(node.right);
                    }
                    if(node.left != null){
                        s1.push(node.left);
                    }
                }
                layer++;
                if(!list2.isEmpty()){
                    listAll.add(list2);
                }
            }
        }
        return listAll;
    }
}