完全二叉树与满二叉树：理解与区别

1、除了最后一层外，每一层的节点都被填满。
2、如果最后一层存在节点，那么这些节点从左到右依次填充，不留空缺。
3、完全二叉树的高度通常较小，具有良好的平衡性。

数组：[1, 2, 3, 4, 5, 6, 7]

对应完全二叉树：
        1
       / \
      2   3
     / \ / \
    4  5 6  7

数组中的第一个元素是树的根节点，即 1。

对于数组中的第 i 个元素，它的左子节点位于数组的第 2*i 个位置，右子节点位于数组的第 2*i+1 个位置。根据这个规则，构建树的其他节点。

左子节点：2*1 = 2，所以根节点 1 的左子节点是 2。
右子节点：2*1+1 = 3，所以根节点 1 的右子节点是 3。
根节点 2 的左子节点是 4，右子节点是 5。
根节点 3 的左子节点是 6，右子节点是 7。
重复上述步骤，直到数组中的所有元素都构建成二叉树。

遍历二叉树，按照层次顺序从上到下、从左到右依次访问节点。
将每个访问的节点的值按照顺序存储到数组中。

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

    TreeNode(int val) {
        this.val = val;
    }
}

public class Convertor {

    // 将数组转换为完全二叉树
    public static TreeNode arrayToCompleteBinaryTree(int[] arr) {
        return arrayToCompleteBinaryTree(arr, 0);
    }

    private static TreeNode arrayToCompleteBinaryTree(int[] arr, int index) {
        if (index >= arr.length) {
            return null;
        }

        TreeNode root = new TreeNode(arr[index]);
        root.left = arrayToCompleteBinaryTree(arr, 2 * index + 1);
        root.right = arrayToCompleteBinaryTree(arr, 2 * index + 2);

        return root;
    }

    // 将完全二叉树转换为数组
    public static int[] completeBinaryTreeToArray(TreeNode root) {
        int height = getHeight(root);
        // 完全二叉树的节点数最大为满二叉树节点数 数组值为默认值0表示无该节点
        int[] arr = new int[(int) Math.pow(2, height) - 1];
        completeBinaryTreeToArray(root, arr, 0);
        return arr;
    }

    private static void completeBinaryTreeToArray(TreeNode root, int[] arr, int index) {
        if (root == null) {
            return;
        }

        arr[index] = root.val;
        completeBinaryTreeToArray(root.left, arr, 2 * index + 1);
        completeBinaryTreeToArray(root.right, arr, 2 * index + 2);
    }

    private static int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6};

        TreeNode root = arrayToCompleteBinaryTree(arr);

        int[] result = completeBinaryTreeToArray(root);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

1、所有层的节点都被填满。
2、满二叉树的高度是固定的，由节点数量决定。

高度为 H 满二叉树节点个数 N：
N = 2^0 + 2^1 + 2^2 + ... + 2^H = 2^H - 1