Friday, February 19, 2016

Indeed: Tree to Array

Buttercola: Indeed: Tree to Array

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``;`
`    ``}`