Print a Binary Tree in Multiple Lines

1. Problem Description

Print a binary tree level by level from top to bottom, with nodes on the same level output from left to right. Output each level on a separate line.

2. Approach

Use a queue for level-order traversal.

3. Implementation

• java

public class 把二叉树打印成多行
{
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot)
    {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot == null)
        {
            return res;
        }
        // Store the data for each line
        ArrayList<Integer> row = new ArrayList<>();
        // Level-order traversal requires a queue
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        // Printing multiple lines requires currentLineLast to record whether the end of the current line has been reached
        TreeNode currentLineLast = pRoot;
        // nextLineLast records the end of the next line
        TreeNode nextLineLast = null;
        // As long as the queue is not empty
        while (!queue.isEmpty())
        {
            // Remove the front node and add it to the current line 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 line list into res
            if (node == currentLineLast)
            {
                res.add(row);
                row = new ArrayList<>();
                currentLineLast = nextLineLast;
            }

        }

        return res;
    }
}

• go

// Time: O(n)
// Space: O(n)
func Print(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)
		}
	}

	return allLines
}

4. References

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