二叉树层序遍历为二维数组

一份执着✘

发布于 2018-06-04 17:16:09

1.4K0

发布于 2018-06-04 17:16:09

文章被收录于专栏：赵俊的Java专栏赵俊的Java专栏

题意

有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。给定二叉树的根结点 root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。保证结点数小于等于 500。

样例

输出结果应为 [[3], [5, 2], [8, 3, 4, 1]]

思路

其实这就是一个二叉树层序遍历的一道题，只不过需要判断什么时候换层了。

可是使用队列来实现，首先声明两个变量 last 和 nlast，last 代表当前层的最右节点，nlast 表示下一行当前已知的最右节点。

先让根节点 3 入队列，然后由于已经是最右节点了，就把 3 赋值给 last，然后分别将队列中的首节点出队列，出队列的元素记作 pollNode，并将该节点的孩子依次入队列（即 5, 2），当放入每一个节点时，都将 nlast 指向这个节点，因为它始终是当前已知的该层的最右节点。当 last == pollNode 表示当前层已遍历完成，然后将 last = nlast ，下一行的开始，直到队列为空。

代码实现

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class TreePrinter {
    public int[][] printTree(TreeNode root) {
        ArrayList<ArrayList<TreeNode>> levelList = new ArrayList<ArrayList<TreeNode>>();
        ArrayList<TreeNode> level = new ArrayList<TreeNode>();

        TreeNode last = root;
        TreeNode nlast = null;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode pollNode = queue.poll();
            level.add(pollNode);
            if (pollNode.left != null) {
                queue.add(pollNode.left);
                nlast = pollNode.left;
            }

            if (pollNode.right != null) {
                queue.add(pollNode.right);
                nlast = pollNode.right;
            }
            if (last == pollNode) {
                last = nlast;
                levelList.add(level);
                level = new ArrayList<TreeNode>();
            }
        }

        int[][] rs = new int[levelList.size()][];
        for (int i = 0; i < levelList.size(); i++) {
            rs[i] = new int[levelList.get(i).size()];
            for (int j = 0; j < rs[i].length; j++) {
                rs[i][j] = levelList.get(i).get(j).val;
            }
        }
        return rs;
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-11-28，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树