按之字形顺序打印二叉树

1. 题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推

2. 思路

就是把二叉树打印成多行.md，这个加上顺序转换即可

3. 实现

• java

public class 按之字形顺序打印二叉树
{
    public 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;
            }

        }

        //如果是奇数行那么转换顺序
        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. 参考

• 按之字形顺序打印二叉树_牛客网
• Binary Tree Zigzag Level Order Traversal - LeetCode