Accepted Java Solution using BFS. Performance in top 10 %tile.


  • 0
    S

    I am using BFS to solve the problem; the only trick is to keep track of the level. If the level is even, use add(E e) to add elements to the end of the nested ArrayList and if it odd then use add(index, E e) with index = 0 to add elements to the front of the ArrayList. So, for level 0,2,4 and so on, elements will be added from left to right, while for level 1,3,5 and so on, elements will be added from right to left.

    NOTE - Performance can be improved if the costly add(index, E e) could have been avoided, which basically shifts each element by one position to the right every time an insert is done, so it is an O(n) operation. Having said that, the solution is within the top 10%tile of all submissions :). I will post an implementation with ArrayDeque later to optimize this performance hit.

    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            helper(root, res, 0);
            return res;
        }
        
        public void helper(TreeNode node, List<List<Integer>> res, int level) {
            if (node == null) return;
            boolean lToR = (level % 2 == 0) ? true : false;
            
            if (level >= res.size()) {
                res.add(new ArrayList<Integer>());
            }
            
            if (lToR) {
                res.get(level).add(node.val); 
            } else {    
                res.get(level).add(0, node.val);
            }
            
            helper(node.left, res, level+1);
            helper(node.right, res, level+1);
        }
    }
    

  • 0

    I think this is the DFS solution. You will traverse the leftmost bunch firstly.


Log in to reply
 

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