[leetcode refers to offer 32 - III. print binary tree III from top to bottom (medium)]

subject ：

Please implement a function to print binary trees in zigzag order , The first line is printed from left to right , The second layer prints from right to left , The third line is printed from left to right , Other lines and so on .

for example :
Given binary tree : [3,9,20,null,null,15,7],

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Return its hierarchical traversal result ：

The problem solving process ①：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    
    List<List<Integer>> node = new ArrayList();
    public List<List<Integer>> levelOrder(TreeNode root) {
    
        bianli(root,0);
        for(int i=1;i<node.size();i+=2){
    
            Collections.reverse(node.get(i));
        }
        return node;
    }

    public void bianli(TreeNode root, int k){
    
        if(root != null){
    
            if(node.size()<=k) node.add(new ArrayList());
            node.get(k).add(root.val);
            bianli(root.left, k+1);
            bianli(root.right, k+1);
        } 
    }
}

Only in the Last question Added a reversal to the result of Collections.reverse(node.get(i));

Execution results ①：

The problem solving process ②：

Ideas come from LeetCode user ： Mai Yuheng
Mainly used arraylist.add（int index,E element） Index from array in index=0 Insert element at .

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    
    List<List<Integer>> node = new ArrayList();
    public List<List<Integer>> levelOrder(TreeNode root) {
    
        bianli(root,0);
        return node;
    }

    public void bianli(TreeNode root, int k){
    
        if(root != null){
    
            if(node.size()<=k) node.add(new ArrayList());
            if(k%2==0){
    
                node.get(k).add(root.val);
            }else{
    
                node.get(k).add(0, root.val);
            }
            bianli(root.left, k+1);
            bianli(root.right, k+1);
        } 
    }
}

Execution results ②：