Indeed: Tree to Array

Buttercola: Indeed: Tree to Array
给定一个Tree, 如何存储这个树来节省空间？

Solution:
Use a binary heap to represent a complete binary tree.

Complete tree: perfectly balanced tree, except for the bottom level. 
Binary heap: Array representation of a heap-ordered complete binary tree. 
Do we need the queue?

    private Queue<TreeNode> nodeQueue = new LinkedList<>();

    private Queue<Integer> indexQueue = new LinkedList<>();

    public Integer[] compressTree(TreeNode root) {

        // step 1: get the height of the tree

        int height = getTreeHeight(root);

        int n = (int) Math.pow(2, height);

        Integer[] array = new Integer[n];

         

        nodeQueue.offer(root);

        indexQueue.offer(1);

         

        while (!nodeQueue.isEmpty()) {

            TreeNode node = nodeQueue.poll();

            int index = indexQueue.poll();

             

            array[index] = node.val;

             

            if (node.left != null) {

                nodeQueue.offer(node.left);

                indexQueue.offer(2 * index);

            }

             

            if (node.right != null) {

                nodeQueue.offer(node.right);

                indexQueue.offer(2 * index + 1);

            }

        }

         

        return array;

    }

     

    private int getTreeHeight(TreeNode root) {

        if (root == null) {

            return 0;

        }

         

        int left = getTreeHeight(root.left);

        int right = getTreeHeight(root.right);

         

        return Math.max(left, right) + 1;

    }

Read full article from Buttercola: Indeed: Tree to Array