如何用层序遍历一个普通的二叉树，并把它以完全二叉树的形式存入数组内呢？为空的地方存入null这种思路

Question

如何用层序遍历一个普通的二叉树，并把它以完全二叉树的形式存入数组内呢？为空的地方存入null这种思路，想了半天都没法实现，

Answer 1

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Test {

    static class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;

        public TreeNode(TreeNode left, TreeNode right, int val) {
            this.left = left;
            this.right = right;
            this.val = val;
        }
    }

    public static void main(String[] args) {
        TreeNode seven = new TreeNode(null, null, 7);
        TreeNode eight = new TreeNode(null, null, 8);
        TreeNode four = new TreeNode(seven, eight, 4);
        TreeNode nine = new TreeNode(null, null, 9);
        TreeNode ten = new TreeNode(null, null, 10);
        TreeNode five = new TreeNode(nine, ten, 5);
        TreeNode two = new TreeNode(four, five, 2);

        TreeNode eleven = new TreeNode(null, null, 11);
        TreeNode twelve = new TreeNode(null, null, 12);
        TreeNode six = new TreeNode(eleven, twelve, 6);
        TreeNode three = new TreeNode(null, six, 3);

        TreeNode one = new TreeNode(two, three, 1);

        levelTraver(one).forEach(e -> System.out.print((e == null ? "null" : e.val) + " "));

    }

    private static List<TreeNode> levelTraver(TreeNode root){
        List<TreeNode> resultList = new ArrayList<>();
        if(root == null) return resultList;
        Queue<TreeNode> q = new LinkedList<>();
        boolean hasChild = false;
        q.offer(root);
        if(root.left != null || root.right != null) hasChild = true;
        while(!q.isEmpty()){
            int len = q.size();
            boolean isAllNull = true;
            boolean nextHasChild = false;
            for(int i = 0; i < len; i++){
                resultList.add((root = q.poll()));
                if(root == null){
                    if(hasChild){
                        q.offer(null);
                        q.offer(null);
                    }
                    continue;
                }
                isAllNull = false;
                if(root.left != null){
                    q.offer(root.left);
                    nextHasChild = true;
                }else if(hasChild){
                    q.offer(null);
                }
                if(root.right != null){
                    q.offer(root.right);
                    nextHasChild = true;
                }else if(hasChild){
                    q.offer(null);
                }
            }
            hasChild = nextHasChild;
            if(isAllNull){
                while(len-- > 0){
                    resultList.remove(resultList.size() - 1);
                }
                break;
            }
        }
        return resultList;
    }
}