二叉树的之字形遍历(层次遍历变形)

落日映苍穹つ 2022-05-18 09:30 289阅读 0赞

![70][]

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));
        }
    }

![这里写图片描述][70 1]

[70]: /images/20220518/9e5204996dcc4e32af0776a6a5329b9c.png
[70 1]: /images/20220518/375a5d7e7e9c47c48b480c1523a7f4fb.png