剑指Offer-按之字形顺序打印二叉树

package Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
 * 思路:
 * 先按层次输出二叉树
 * 判断奇数层和偶数层
 * 反转arrayList
 */
public class Solution9 {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        Solution9 Solution9 = new Solution9();
        TreeNode treeNode = Solution9.createBinaryTreeByArray(array, 0);
        for (ArrayList list :
                Solution9.Print(treeNode)) {
            System.out.println(list);
        }
    }

    /**
     * 之字形打印二叉树
     * 用reserve反转,时间复杂度高
     *
     * @param pRoot
     * @return
     */
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        //arrayLists存储结果
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        if (pRoot == null) {
            return arrayLists;
        }
        ArrayList<Integer> arrayList = new ArrayList<>();
        //使用队列,先进先出
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        int start = 0;
        int end = 1;
        boolean leftToRight = true;
        while (!queue.isEmpty()) {
            TreeNode temp = queue.remove();
            //添加到本行的arrayList
            arrayList.add(temp.val);
            start++;
            //每打印一个节点,就把此节点的下一层的左右节点加入队列,并记录下一层要打印的个数
            if (temp.left != null) {
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }

            if (start == end) {
                start = 0;
                end = queue.size();
                if (leftToRight) {
                    arrayLists.add(arrayList);
                } else {
                    arrayLists.add(reverse(arrayList));

                }
                leftToRight = !leftToRight;
                arrayList = new ArrayList<>();
            }
        }
        return arrayLists;
    }

    /**
     * 反转
     *
     * @param arrayList
     * @return
     */
    private ArrayList<Integer> reverse(ArrayList<Integer> arrayList) {
        ArrayList<Integer> arrayList1 = new ArrayList<>();
        for (int i = arrayList.size() - 1; i >= 0; i--) {
            arrayList1.add(arrayList.remove(i));
        }
        return arrayList1;
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    /**
     * 数据转二叉树
     *
     * @param array
     * @param index
     * @return
     */
    private TreeNode createBinaryTreeByArray(int[] array, int index) {
        TreeNode tn = null;
        if (index < array.length) {
            int value = array[index];
            tn = new TreeNode(value);
            tn.left = createBinaryTreeByArray(array, 2 * index + 1);
            tn.right = createBinaryTreeByArray(array, 2 * index + 2);
            return tn;
        }
        return tn;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题39判断平衡二叉树

题目:输入一颗二叉树的根结点,判断该树是不是平衡二叉树。 如果某二叉树中任意结点的左右子树的高度相差不超过1,那么它就是一棵平衡二叉树。 分析:所谓平衡二...

30450
来自专栏null的专栏

数据结构和算法——二叉树

二叉树是使用较多的一种树形结构,如比较经典的二叉排序树,Huffman编码等,都使用到了二叉树的结构,同时,在机器学习算法中,基于树的学习算法中也大量使用到二叉...

31750
来自专栏xcywt

《大话数据结构》树以及赫夫曼编码的例子

第六章 树 6.2 树的定义 树(Tree)的n个结点的有限集。当n=0时,称为空树。 任意一个非空树中: 1)有且仅有一个特定的称为根(root)的结点 2)...

46060
来自专栏java学习

让你更好的理解什么是二叉树?

二叉树 6.2.1 二叉树的概念 二叉树(Binary Tree)是结点的有限集合,这个集合或者为空,或者是由一个根结点和两颗互不相交的分别称为左子树和右子树的...

804110
来自专栏用户画像

4.3.1 二叉树的遍历

所谓二叉树的遍历,是指按照某条搜索路径访问树中的每个结点,使得每个几点均被访问一次,而且仅被访问一次。

9320
来自专栏武培轩的专栏

剑指Offer-平衡二叉树

package Tree; /** * 平衡二叉树 * 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 * 平衡二叉树(Balanced Binary ...

30770
来自专栏C/C++基础

判断二叉树是否为平衡二叉树

解题思路: 根据二叉树的定义,我们可以递归遍历二叉树的每一个节点来,求出每个节点的左右子树的高度,如果每个节点的左右子树的高度相差不超过1,按照定义,它就是...

8120
来自专栏weixuqin 的专栏

数据结构学习笔记(树、二叉树)

27030
来自专栏猿人谷

判断二叉树是不是平衡

平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超...

21560
来自专栏用户画像

4.3.2 线索二叉树

二叉树结点的各种遍历序列,其实质是对一个非线性结构进行线性化操作,使在这个访问序列中每一个结点(除第一个和最后一个)都有一个直接前驱和直接后继。

11920

扫码关注云+社区

领取腾讯云代金券