Java实现带行号层序遍历二叉树的变种问题（使用二维数组保存）

2019-11-06 09:23:59

字体：大中小

来源：转载

供稿：网友

　　最近在看面试题的时候发现，一些基础的算法都记不住了，只是能大概说出个原理….为了加深记忆，这里对一些简单的算法题进行一个归纳。

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

测试用例样例：　　输入：节点值为1-7的满二叉树。　　预期结果：　　　　　　[1 ] 　　　　　　[2,3] 　　　　　　[4,5,6,7]

　　下面是java实现：

import java.util.*;/** * Created by Flynnon on 17-2-27. * 问题：有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。 * 给定二叉树的根结点root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列. */public class BinaryTreeUtil { /** * 定义节点类 * 为了简单就不定义getter/setter方法了 */ public static class Node { public Node(){ this(0); } public Node(int v){ value = v; } int value; Node left = null; Node right = null; } /** * 进行转化的工具类 * 主要思路：主要思路与带行号层序遍历二叉树类似，只是用可变长数组（List）来存储每一行的元素 * @param root 要遍历的二叉树的根节点 * @return 此二叉树转化成的二维数组 */ public static int[][] getTreeValueArray(Node root) { // 保证这颗二叉树非空 if (root == null) { return new int[][]{}; } // curLineLast : 当前行结尾节点 // nextLineLast : 下一行结尾节点 // 刚开始时，curLineLast与nextLineLast均指向根节点 Node curLineLast = root, nextLineLast = root; Queue<Node> q = new LinkedList<>(); q.add(root); // 外层 List<List<Integer>> lists = new ArrayList<>(); // 内层 List<Integer> list = new ArrayList<>(); while (!q.isEmpty()) { Node temp = q.poll(); // 只有当前节点的子节点不为空时，nextLineLast才需要更改指向的目标 if (temp.left != null) { q.add(temp.left); nextLineLast = temp.left; } if (temp.right != null) { q.add(temp.right); nextLineLast = temp.right; } // 将当前节点（值）加入内层 list.add(temp.value); // 当出栈节点为当前行尾节点时，说明该换行了 if (curLineLast == temp) { // 换行时将内层加入到外层中 lists.add(list); // 新初始化一个内层 list = new ArrayList<>(); // 将当前行尾节点指向下一行尾节点 curLineLast = nextLineLast; } } // 将得到的List转化为int[] int[][] ints = new int[lists.size()][]; for (int i = 0; i < ints.length; i++) { Integer[] integerArray = lists.get(i).toArray(new Integer[0]); ints[i] = new int[integerArray.length]; for (int j=0;j<integerArray.length;j++){ ints[i][j] = integerArray[j]; } } return ints; } /** * 前序递归构造二叉树 root->left->right * * @param scanner 输入流，用于读取节点值 * @return 构造完成的二叉树的根节点 */ public static Node createTreeNode(Scanner scanner) { assert scanner != null; Node root = null; //声明当前根节点 int data = scanner.nextInt(); if (data > 0) { //若当前节点存在（这里为了简单以负数为占位符） root = new Node(data); //使用其它顺序构造二叉树，只需更改这三句即可 root.left = createTreeNode(scanner); root.right = createTreeNode(scanner); } return root; } /** * 测试类 * 以1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1为例 */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); Node root = Test.createTreeNode(sc); sc.close(); int[][] result = BinaryTreeUtil.getTreeValueArray(root); for (int[] arr : result) { System.out.PRintln(Arrays.toString(arr)); } }}

下面是测试用例及结果，与预期结果一致。

测试结果