Simple Java Solution With Explanation

  • 0

    For this problem I wanted to use as much of the standard "Level Order Traversal" Algorithm as possible. I went with the BFS level order algorithm with a slight modification. If we take a look at the zigzag property its nothing more than alternating which end of the temp list is being added to (either the front or the back). This is a simple spec to code for. I kept a variable level and before adding to a given levels list i check rather the level variable is odd or even. If Odd I add to the front of the list if even I add to the back.

    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> levels = new ArrayList<List<Integer>>();
            if(root == null) return levels;
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            int level = 0;
                int size = q.size();
                List<Integer> list = new ArrayList<Integer>();
                for(int i = 0; i < size; i++){
                   TreeNode n = q.remove();
                   if(level % 2 == 1){
                   if(n.left != null) q.add(n.left);
                   if(n.right != null) q.add(n.right);
            return levels;

Log in to reply

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