剑指Offer-把二叉树打印成多行

package Tree;


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

/**
 * 从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
 * 思路:
 * 按层次输出二叉树
 * 访问根节点,并将根节点入队。
 * 当队列不空的时候,重复以下操作。
 * 1、弹出一个元素。作为当前的根节点。
 * 2、如果根节点有左孩子,访问左孩子,并将左孩子入队。
 * 3、如果根节点有右孩子,访问右孩子,并将右孩子入队。
 */
public class Solution8 {

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        Solution8 solution8 = new Solution8();
        TreeNode treeNode = solution8.createBinaryTreeByArray(array, 0);
        for (ArrayList list :
                solution8.Print(treeNode)) {
            System.out.println(list);
        }
    }


    /**
     * 层次遍历
     *
     * @param pRoot 根节点
     * @return arrayLists
     */
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        //存放结果
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        if (pRoot == null) {
            return arrayLists;
        }
        //使用队列,先进先出
        Queue<TreeNode> queue = new LinkedList<>();
        //存放每行的列表
        ArrayList<Integer> arrayList = new ArrayList<>();
        //记录本层打印了多少个
        int start = 0;
        //记录下层打几个
        int end = 1;
        queue.add(pRoot);
        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) {
                //此时的queue中存储的都是下一层的节点,则end即为queue大小
                end = queue.size();
                start = 0;
                //把arrayList添加到结果列表arrayLists中
                arrayLists.add(arrayList);
                //重置arrayList
                arrayList = new ArrayList<>();
            }
        }

        return arrayLists;
    }



    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;
    }


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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏撸码那些事

【图解数据结构】二叉查找树

1192
来自专栏mathor

LeetCode110.平衡二叉树

 平衡二叉树的定义是一个二叉树每个结点的左右两个子树的高度差绝对值不超过1(可以是1),用一个结构体来保存某个结点的信息(包括是否是平衡树,高度多少),算法...

1033
来自专栏彭湖湾的编程世界

【算法】论平衡二叉树(AVL)的正确种植方法

《算法(java)》                           — — Robert Sedgewick, Kevin Wayne

1112
来自专栏desperate633

LintCode 二叉树的层次遍历 II题目代码

给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历)

944
来自专栏desperate633

LintCode 平衡二叉树题目分析代码

给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深度相差不会超过1。

722
来自专栏Python专栏

【数据结构与算法】一起搞定面试中的二叉树题目(二)

2073
来自专栏weixuqin 的专栏

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

2623
来自专栏日常分享

Java 通过先序中序序列生成二叉树

  二叉树的前序以及后续序列,以空格间隔每个元素,重构二叉树,最后输出二叉树的三种遍历方式的序列以验证。

1611
来自专栏书山有路勤为径

二叉查找树转换为较大树

Leetcode 538 已知一个二叉查找树,将它转换为一个较大树,即所有的二叉查找树的节点,赋值为该节点本身的值与该节点大的节点的值的和

852
来自专栏武培轩的专栏

剑指Offer-二叉树中和为某一值的路径

题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 思路 回...

3104

扫码关注云+社区

领取腾讯云代金券