博客

 import java.util.ArrayList;
 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> arr=new ArrayList<ArrayList<Integer>>();
        if(root==null)
         return arr; 

        zigzagLevelHelper(root,0,arr);
        return arr;
    }

    //递归版实现二叉树的层次遍历(之字形遍历)
    public  void zigzagLevelHelper(TreeNode root,int level, ArrayList<ArrayList<Integer>> arr){
        if(root==null)
           return ;
         if(level==arr.size()){
            ArrayList<Integer>newlevelResult=new ArrayList<>();
            if(level%2==0)                   //偶数层
                newlevelResult.add(root.val);
            else                             //奇数层
                newlevelResult.add(0,root.val); 
            arr.add(newlevelResult);
         }else{
            ArrayList<Integer>levelResult=arr.get(level);
            if(level%2==0)      
                levelResult.add(root.val);
            else
                levelResult.add(0,root.val);
            arr.set(level,levelResult);
         }
         //递归遍历左右节点
         zigzagLevelHelper(root.left,level+1,arr);
         zigzagLevelHelper(root.right,level+1,arr); 
    }

    public static void main(String[]args){
       //System.out.println("Hello Wolrd!");
      TreeNode root=new TreeNode(3);
       root.left=new TreeNode(9);
       root.right=new TreeNode(20);
       root.right.left=new TreeNode(15);
       root.right.right=new TreeNode(7);
       Solution s=new Solution();
       System.out.println(s.zigzagLevelOrder(root));
    }
}