Day 66 of 100 Days of code

1.Binary Tree Zigzag Level Order Traversal

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> q=new LinkedList<>();
        List<List<Integer>> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        q.offer(root);
        boolean flag=true;
        while(!q.isEmpty()){
            int level=q.size();
            ArrayList<Integer> sub=new ArrayList<>();
            for(int i=0;i<level;i++){
                if(q.peek().left!=null){q.offer(q.peek().left);}
                if(q.peek().right!=null){q.offer(q.peek().right);}
                if(flag==true){sub.add(q.poll().val);}
                else{sub.add(0,q.poll().val);}
            }
            flag=!flag;
            list.add(sub);
        }
        return list;
    }
    
}        

TC: O(N)

SC: O(N)

2.Sum Root to Leaf Numbers

class Solution {
    public static int total;
    public int sumNumbers(TreeNode root) {
        total=0;
        helper(root,0);
        return total;
    }
    public static void helper(TreeNode root,int sum){
        if(root==null){return;}
        sum=10*sum+root.val;
        if(root.left==null &&root.right==null){
            total+=sum;
        }
        helper(root.left,sum);
        helper(root.right,sum);
    }
}        

TC: O(N)

SC: O(N)

3.Diameter of Binary Tree

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        int []diameter=new int[1];
        height(root,diameter);
        return diameter[0];
    }
    public static int height(TreeNode root,int[] diameter){
        if(root==null){
            return 0;
        }
        int lh= height(root.left,diameter);
        int rh= height(root.right,diameter);
        diameter[0]=Math.max(diameter[0],lh+rh);
        return 1+Math.max(lh,rh);
    }
}        

TC: O(N)

SC: O(N)