JAVA recursive solution 1ms


  • 0
    M
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            int h = height(root);
            List<List<Integer>> mainList = new LinkedList<List<Integer>>();
            /*Store each level starting from the root*/
            for(int i=0;i<h;i++){
                List<Integer> levelList = new LinkedList<Integer>();
                printLevel(root,i,levelList,(i+1)%2);
                mainList.add(levelList);
                
            }
            return mainList;
        }
        /*Parse each level*/
        private void printLevel(TreeNode root,int level,List<Integer> levelList,int reverse){
            if(root == null)
                return;
            if(level == 0){
                levelList.add(root.val);
                return;
            }
            /*If even level parse from left to right. If odd level parse from right to left*/
            if(reverse == 1){
                printLevel(root.left,level-1,levelList,1);
                printLevel(root.right,level-1,levelList,1);
            }
            else{
                printLevel(root.right,level-1,levelList,0);
                printLevel(root.left,level-1,levelList,0);
            }
        }
        /*Calculate the height of tree*/
        private int height(TreeNode root){
            if(root == null)
                return 0;
            int lh = height(root.left);
            int rh = height(root.right);
            if(lh>rh){
                return 1+lh;
            }
            else{
                return 1+rh;
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.