题解 | #按之字形顺序打印二叉树#

import java.util.ArrayList;

/*
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>> result = new ArrayList<>(); // 用来保存结果
        dg(pRoot, 0, result);
        for (int i = 1; i < result.size(); i+=2) {
            ArrayList<Integer> heightList = result.get(i);
            for (int j = 0; j < heightList.size()/2; j++) { // 将奇数层结果前后颠倒
                Integer tmp = heightList.get(j);
                int right = heightList.size() - j - 1;
                heightList.set(j, heightList.get(right));
                heightList.set(right, tmp);
            }
        }
        return result;
    }

    /**
     * 将当前节点加入到结果集合，并递归遍历子节点
     * @param cur 当前节点
     * @param height 当前节点高度
     * @param result 结果集
     */
    private void dg(TreeNode cur, int height, ArrayList<ArrayList<Integer>> result){
        if(cur==null) return; //到底了
        ArrayList<Integer> heightList; // 当前这一层的结果集
        if(result.size()>height) {
            heightList = result.get(height);
        } else {
            heightList = new ArrayList<>();
            result.add(heightList);
        }
        heightList.add(cur.val);
        dg(cur.left, height + 1, result);
        dg(cur.right, height + 1, result);
    }
}