从上到下打印二叉树系列题目
1.剑指 Offer 32 - I. 从上到下打印二叉树(java解题)
2.剑指 Offer 32 - II. 从上到下打印二叉树 II(java解题)

1. 题目

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

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

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

提示:

节点总数 <= 1000

作者:Krahets
链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/5vnp91/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

2. 解题思路

剑指 Offer 32 - II. 从上到下打印二叉树 II(java解题) 类似,在基础层次遍历的基础上,处理每一层的节点。

这里从左往右和从右往左两种进出队列的方式,要求我们在本题中使用双端队列,之前均使用LinkedList来模拟队列,而LinkedList中也有addLast()addFirst()removeFirst()removeLast()等插删操作可以模拟双端队列。

题目描述提示我们,对每一层的节点有两种处理方式,若节点层从1开始计数,则1、3、5等奇数层从左往右处理,2、4、6等偶数层从右往左处理,故使用layer变量记录当前层数。

  • 从左往右处理是之前的解题中默认的处理思路,在队列头部出队,将出队节点的左右子树节点存放在队列尾部。

  • 从右往左处理需要一些思维上的转变。首先是节点出队,应当是从队列尾部出队,之后考虑出队节点的左右子树节点如何入队,为了和目前的出队顺序不矛盾,应当在队列头部入队;并且为了保证下一层队列头部出队(从左往右)的顺序,应该右子树节点先入队,然后左子树节点入队。

3. 数据类型功能函数总结

//LinkedList
LinkedList<E> listname=new LinkedList<E>();//初始化
LinkedList.add(elment);//在链表尾部添加元素
LinkedList.addFirst(elment);//在链表头部添加元素
LinkedList.removeFirst();//取出链表头部元素
LinkedList.removeLast();//取出链表尾部元素
LinkedList.size();//获取元素个数
//ArrayList
ArrayList<E> listname=new ArrayList<E>();//初始化
ArrayList.add(elment);//在数组最后插入元素
//List<List<Integer>>
List<List<Integer>> name=new ArrayList<>();//或者是 = new LinkedList<>()
//错误写法: List<List<Integer>> name=new List<List<Integer>>();

4. java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //之字形打印每一层--双端队列--linkedlist实现,需要注意的是子节点放入的顺序
    //奇数行按照从左往右,偶数行按照从右往左
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
        if(root==null){
            return result;
        }
        else{
            queue.add(root);
            int layer=1;
            while(queue.size()!=0){
                int size=queue.size();
                ArrayList<Integer> temp=new ArrayList<>();
                while(size>0){
                    if(layer%2!=0){//奇数层
                        //从左往右
                        TreeNode node=queue.removeFirst();
                        temp.add(node.val);
                        if(node.left!=null){
                            queue.add(node.left);
                        }
                        if(node.right!=null){
                            queue.add(node.right);
                        }
                    }
                    else{//偶数层
                        //从右往左
                        TreeNode node=queue.removeLast();
                        temp.add(node.val);
                        if(node.right!=null){
                            queue.addFirst(node.right);
                        }
                        if(node.left!=null){
                            queue.addFirst(node.left);
                        }

                    }
                   
                    size--;
                }
                result.add(temp);
                layer+=1;
            }
            return result;
        }

    }
}