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

下面是測試用例及結果，與預期結果一致。

測試結果