An easy understanding java solution based on level order traversal

  • 0
    public class Solution {
        //add modification to levelorder traversel: for levels from left to right, add next node to the end of list
        //for levels from right to left, add next node to the front of the list
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result = new LinkedList<>();
            if(root == null)    return result;
            Queue<TreeNode> q = new LinkedList<>();
            boolean leftToRight = true;    //root level is left to right
                int size = q.size();
                List<Integer> list = new LinkedList<>();
                for(int i = 0; i < size; i++){
                    TreeNode node = q.poll();
                        list.add(0, node.val);
                    if(node.left != null)   q.offer(node.left);
                    if(node.right != null)  q.offer(node.right);
                leftToRight = !leftToRight;
            return result;

Log in to reply

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