Print a Binary Tree in Zigzag Order

1. Problem Description

Implement a function that prints a binary tree in zigzag order: the first row from left to right, the second level from right to left, the third row from left to right, and so on.

2. Approach

It is just Print a Binary Tree in Multiple Lines with an additional order conversion.

3. Implementation

• java

public class 按之字形顺序打印二叉树
{
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot)
    {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot == null)
        {
            return res;
        }

        // Store the data for each row
        ArrayList<Integer> row = new ArrayList<>();
        // Level-order traversal requires a queue
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        // Printing multiple rows requires currentLineLast to record whether the end of the current row has been reached
        TreeNode currentLineLast = pRoot;
        // nextLineLast records the end of the next row
        TreeNode nextLineLast = null;
        // As long as the queue is not empty
        while (!queue.isEmpty())
        {
            // Remove the front node and add it to the current row list
            TreeNode node = queue.removeFirst();
            row.add(node.val);
            // Enqueue the left node and update nextLineLast
            if (node.left != null)
            {
                queue.add(node.left);
                nextLineLast = node.left;
            }
            // Enqueue the right node and update nextLineLast
            if (node.right != null)
            {
                queue.add(node.right);
                nextLineLast = node.right;
            }
            // If the current node reaches currentLineLast, update currentLineLast and save the current row list into res
            if (node == currentLineLast)
            {
                res.add(row);
                row = new ArrayList<>();
                currentLineLast = nextLineLast;
            }

        }

        // Reverse the order for odd-indexed rows
        for (int i = 0; i < res.size(); i++)
        {
            if (i % 2 == 1)
            {
                Collections.reverse(res.get(i));
            }
        }

        return res;
    }
}

• go

func Print2(pRoot *TreeNode) [][]int {
	if pRoot == nil {
		return nil
	}

	allLines := make([][]int, 0)
	line := make([]int, 0)
	queue := make([]*TreeNode, 0)
	queue = append(queue, pRoot)
	currentLineLast := pRoot
	var nextLineLast *TreeNode
	for len(queue) > 0 {
		removed := queue[0]
		queue = queue[1:]
		line = append(line, removed.Val)
		if removed.Left != nil {
			queue = append(queue, removed.Left)
			nextLineLast = removed.Left
		}
		if removed.Right != nil {
			queue = append(queue, removed.Right)
			nextLineLast = removed.Right
		}
		if removed == currentLineLast {
			currentLineLast = nextLineLast
			allLines = append(allLines, line)
			line = make([]int, 0)
		}
	}

	for i := 0; i < len(allLines); i++ {
		if i%2 == 1 {
			reversed(allLines[i])
		}
	}

	return allLines
}

func reversed(data []int) {
	i := 0
	j := len(data) - 1
	for i < j {
		data[i], data[j] = data[j], data[i]
		i++
		j--
	}
}

4. References

• Print a Binary Tree in Zigzag Order - NowCoder
• Binary Tree Zigzag Level Order Traversal - LeetCode