把二叉树打印成多行

1. 题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

2. 思路

层序遍历使用队列

3. 实现

• java

public class 把二叉树打印成多行
{
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot)
    {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot == null)
        {
            return res;
        }
        //保存每一行的数据
        ArrayList<Integer> row = new ArrayList<>();
        //层序遍历需要使用队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        //打印成多行需要一个变量currentLineLast记录是否到达了末尾
        TreeNode currentLineLast = pRoot;
        //还得有一个变量nextLineLast记录下一行的末尾
        TreeNode nextLineLast = null;
        //只要队列不为空
        while (!queue.isEmpty())
        {
            //取出队首，加入当前行的list
            TreeNode node = queue.removeFirst();
            row.add(node.val);
            //把左节点入队，并更新nextLineLast
            if (node.left != null)
            {
                queue.add(node.left);
                nextLineLast = node.left;
            }
            //把右节点入队，并更新nextLineLast
            if (node.right != null)
            {
                queue.add(node.right);
                nextLineLast = node.right;
            }
            //看当前节点是否到达了currentLineLast，是的话更新currentLineLast并且保存当前行的list到res
            if (node == currentLineLast)
            {
                res.add(row);
                row = new ArrayList<>();
                currentLineLast = nextLineLast;
            }

        }

        return res;
    }
}

• go

//时间：O(n)
//空间：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. 参考

• 把二叉树打印成多行_牛客网
• Binary Tree Level Order Traversal - LeetCode