Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Solution: Use two linked list to represent curr level and the next level. While iterating through the node on the current level, we put the child nodes to next level in order based on if the current level is odd or even.

If current is odd level, so next level should be right->left, so we always insert right node in front of left node.

If current is even level, so next level should be left->right, we always insert left node in front of right node.

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> curr = new LinkedList<>();
        LinkedList<TreeNode> next = new LinkedList<>();
        curr.add(root);
        while (!curr.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            while (!curr.isEmpty()) {
                TreeNode node = curr.remove();
                tmp.add(node.val);
                //current is odd level
                //so next level should be right->left
                if (res.size() % 2 == 0) {
                    if (node.left != null) {
                        next.add(0, node.left);
                    }
                    if (node.right != null) {
                        next.add(0, node.right);
                    }
                }
                //current is even level
                //so next level should be left->right
                else {
                    if (node.right != null) {
                        next.add(0, node.right);
                    }
                    if (node.left != null) {
                        next.add(0, node.left);
                    }
                }
            }
            curr = next;
            next = new LinkedList<>();
            res.add(tmp);
        }
        return res;
    }
FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *