[数据结构与算法]把二叉树打印成多行

题目

• 把二叉树打印成多行

解法

• 构建二叉树

public class BSTNode<T extends Comparable<T>> {
    T key;
    BSTNode<T> left;
    BSTNode<T> right;
    BSTNode<T> parent;

    public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
        this.key = key;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }
}

• 使用循环实现

    /**
     * 从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印一行
     *
     * @param tree
     */
    public static void printTreeMultiLines(BSTNode<Integer> tree) {
        if (tree == null) {
            return;
        }

        List<BSTNode> mList = new LinkedList<>();
        int number = 1;
        int size = 0;
        mList.add(tree);

        while (mList.size() > 0) {
            // 当前结点
            BSTNode currentNode = mList.remove(0);
            number--;
            System.out.print(currentNode.key + "  ");

            // 左子树
            if (currentNode.left != null) {
                mList.add(currentNode.left);
                size++;
            }

            // 右子树
            if (currentNode.right != null) {
                mList.add(currentNode.right);
                size++;
            }
            // 重置
            if (number == 0) {
                System.out.println();
                number = size;
                size = 0;
            }

        }

    }

• 使用递归实现

/**
     * 通过递归方式打印
     *
     * @param tree
     */
    public static void printTreeMultiLineRecursive(BSTNode<Integer> tree) {
        List<ArrayList<Integer>> list = new ArrayList<>();
        depthAddData(tree, 1, list);
        for (ArrayList i : list) {
            System.out.println(i);
        }
    }

    private static void depthAddData(BSTNode<Integer> tree, int depth, List<ArrayList<Integer>> list) {
        if (tree == null) return;
        if (depth > list.size()) {
            list.add(new ArrayList<>());
        }
        list.get(depth - 1).add(tree.key);

        depthAddData(tree.left, depth + 1, list);
        depthAddData(tree.right, depth + 1, list);
    }

• 参考：牛客网