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

  • 自己做了,没做出来,看了别人的实现,自己写了一遍,参考:https://blog.nowcoder.net/n/ce221364d0a644d49277c3623a6b8c26?f=comment

  • 思路:

    • 二叉树层级遍历,分层加入队列;

    • 从队列中取出来节点,把节点值加入子集合,子集合加入总集合;

    • 增加标记位,标记是否需要反转;

      public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
      
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        if (pRoot == null) {
            return arrayLists;
        }
        // 创建队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        boolean reverse = false;
        queue.add(pRoot);
        while (!queue.isEmpty()) {
            // 每一层new一个集合
            ArrayList<Integer> list = new ArrayList<>();
      
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 队列中循环弹出节点;
                TreeNode node = queue.poll();
                if (node == null) {
                    continue;
                }
                // 判断是否需要反转,如果需要,总是将节点值加到list的0位置
                if (!reverse) {
                    list.add(node.val);
                } else {
                    list.add(0, node.val);
                }
                // queue中加入下一层级的节点,循环的过程中会把下一层所有节点加到队列
                queue.add(node.left);
                queue.add(node.right);
            }
            // 是否取反,标记位取反
            reverse = !reverse;
            if(list.size() != 0){
                arrayLists.add(list);
            }
         }
        return arrayLists;
      }