convert integer array into a binary tree
13,679
Solution 1
Here is a java-monster and it solves the task with the possibility of debugging
import java.util.*;
public class TreeCreator {
public static void main(String[] args) {
Integer[] tree = new Integer[]{1, null, 2, 3};
TreeCreator tr = new TreeCreator();
TreeNode treeNode = tr.fromArray(tree);
List<Integer> list = tr.postorderTraversal(treeNode);
list.forEach(System.out::println); // postOrder is 3 2 1
}
public TreeNode fromArray(Integer[] tree) {
if (tree.length == 0) return null;
TreeNode root = new TreeNode(tree[0]);
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
for (int i = 1; i < tree.length; i++) {
TreeNode node = q.peek();
if (node.left == null) {
node.left = new TreeNode(tree[i]);
if (tree[i] != null) q.add(node.left);
} else if (node.right == null) {
node.right = new TreeNode(tree[i]);
if (tree[i] != null) q.add(node.right);
q.remove();
}
}
return root;
}
private static class TreeNode {
Integer val;
TreeNode left;
TreeNode right;
TreeNode(Integer x) {
val = x;
}
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> l = new ArrayList<>();
if (root == null) return l;
funcPostOrder(root, l);
return l;
}
private void funcPostOrder(TreeNode c, List<Integer> l) {
if (c.left != null && c.left.val != null) {
funcPostOrder(c.left, l);
}
if (c.right != null) {
funcPostOrder(c.right, l);
}
l.add(c.val);
}
}
more interesing example is
Integer[] tree = new Integer[]{5,4,8,11,null,13,4,7,2,null,null,null,1};
Solution 2
If you read the tree in preorder, you will find 1, -, 2, 3, -
. Just construct the tree using the same order and not looking up the string at index*2
and index*2+1
, but left to right. (You can discard the final nulls if you like).
For a more "complex" example:
1
/ \
2 3
\ / \
4 5 6
7 8
1, 2, -, 4, 3, 5, -, 7, 6, -, 8
Author by
rekinyz
Updated on June 04, 2022Comments
-
rekinyz almost 2 years
I can already convert an array into a binary tree using following algorithm in java:
public class TreeNode { public TreeNode left, right; public int val; public TreeNode(int val) { this.val = val; } } public TreeNode arrayToTree(Integer[] input){ TreeNode root = createTreeNode(input,1); return root; } private TreeNode createTreeNode(Integer[] input, int index){ if(index<=input.length){ Integer value = input[index-1]; if(value!=null){ TreeNode t = new TreeNode(value); t.left = createTreeNode(input, index*2); t.right = createTreeNode(input, index*2+1); return t; } } return null; }
when the input is {1,null,2,null,null,3}, I get following tree:
1 \ 2 / 3
however I think the input {1,null,2,3} is clear enough to define a tree like above.
Any good idea to avoid the redundant nulls defined in the input array?
-
zfgo over 3 yearsthis is not correct, using {1, null,2, 3} gives null pointer exception in fromArray