Java O(n) 1ms with preorder traversal


  • 0
    R
    public class Solution {
        List<List<Integer>> list;
        int findheight(TreeNode root){
            if(root==null) return 0;
            return 1+Math.max(findheight(root.left),findheight(root.right));
        }
        
        void preorder(TreeNode root,int level){
            if(root==null) return;
            list.get(level).add(root.val);
            preorder(root.left,level+1);
            preorder(root.right,level+1);
            
        }
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            int h = findheight(root);
            list = new ArrayList<List<Integer>>(h);
            for(int i=0;i<h;i++){
                list.add(new ArrayList<Integer>());
            }
            preorder(root,0);
            for(int i=0;i<h;i++){
                if(i%2==1){
                    Collections.reverse(list.get(i));
                }
            }
            return list;
        }
    }

  • 0
    R

    Beats 91% of the Java sollutions runtime


Log in to reply
 

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