Simple and clean Java, with direction flag to control output of the level order traversal


  • 0
    J
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null)
        	return ans;
        boolean directionFlag = true; //true: left to right; false : from right to left.
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
        	int len = queue.size();
        	TreeNode node;
       		LinkedList<Integer>  olist = new LinkedList<>();
        	for (int i = 0; i < len; i++) {
        		node = queue.poll();
        		if (directionFlag) {
        			olist.addLast(node.val);
        		} else {
        			olist.addFirst(node.val);
        		}
        		if (node.left != null) queue.offer(node.left);
        		if (node.right != null) queue.offer(node.right);
        	}
       		ans.add(olist);
        	directionFlag = !directionFlag;
        }
        return ans;
    }

Log in to reply
 

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