/**
     * 复制二叉树
     * @param root
     * @return
     */
    public static TreeNode copyTree(TreeNode root){
        TreeNode node = null;
        if(root == null) return null;
        node = new TreeNode(root.data);
        node.leftChild = copyTree(root.leftChild);
        node.rightChild = copyTree(root.rightChild);
        return node;
    }

package treenode;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * User:Mr.Du
 * Date:2021/8/20
 * Time:18:42
 */
public class CopyTreeNode {


    public static void main(String[] args) {
        int input = 0;
        LinkedList<Integer> list = new LinkedList<>();
        Scanner sc = new Scanner(System.in);
        //当输入-1时，表示结束输入
        while(sc.hasNextLine()){
            if((input = sc.nextInt()) != -1){
                list.add(input);
            }else {
                break;
            }
        }

        TreeNode binaryTree = createBinaryTree(list);
        System.out.println("层序遍历输出创建的二叉树");
        List<List<Integer>> lists = levelOrder(binaryTree);
        printTreeNode(lists);
        System.out.println("========================");
        //copy
        TreeNode newTree = copyTree(binaryTree);
        System.out.println("复制后输出新的二叉树 newTree :");
        List<List<Integer>> newTreeList = levelOrder(newTree);
        printTreeNode(newTreeList);
    }

    /**
     * 创建二叉树
     * @param list
     * @return
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> list){
        TreeNode node = null;
        if(list == null || list.isEmpty()){
            return null;
        }
        Integer data = list.removeFirst();
        //0表示当前结点为空
        if(data != 0){
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(list);
            node.rightChild = createBinaryTree(list);
        }
        return node;
    }

    /**
     * 层序遍历，将每层结果放在一个集合，方便查看结果
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 0;
        while ( !queue.isEmpty() ) {
            // start the current level
            levels.add(new ArrayList<>());

            // number of elements in the current level
            int level_length = queue.size();
            for(int i = 0; i < level_length; ++i) {
                TreeNode node = queue.remove();

                // fulfill the current level
                levels.get(level).add(node.data);

                // add child nodes of the current level
                // in the queue for the next level
                if (node.leftChild != null) queue.add(node.leftChild);
                if (node.rightChild != null) queue.add(node.rightChild);
            }
            // go to next level
            level++;
        }
        return levels;
    }


    public static void printTreeNode(List<List<Integer>> list){
        for(List l : list){
            System.out.println(l);
        }
    }
}