我已经可以使用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;
}
当输入为 {1,null,2,null,null,3} 时，我得到以下树：
1
\
2
/
3
但是我认为输入 {1,null,2,3} 足够清晰，可以定义像上面这样的树。
有什么好主意可以避免输入数组中定义的冗余 nulls 吗？
这是一个java-monster，它解决了具有调试可能性的任务
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);
}
}
更有趣的例子是
Integer[] tree = new Integer[]{5,4,8,11,null,13,4,7,2,null,null,null,1};
如果您按顺序阅读树，您会发现
1, -, 2, 3, -index*2index*2+1对于更“复杂”的示例：
1
/ \
2 3
\ / \
4 5 6
7 8
1, 2, -, 4, 3, 5, -, 7, 6, -, 8
这应该可以解决问题。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
static TreeNode arrayToTree(Integer array[]) {
return arrayToTree(array, 0);
}
static TreeNode arrayToTree(Integer array[], int index) {
if (index >= array.length)
return null;
if (array[index] == null)
return null;
return new TreeNode(array[index], arrayToTree(array, index * 2 + 1), arrayToTree(array, index * 2 + 2));
}
这是一个java-monster，它解决了具有调试可能性的任务
使用 Integer 来防止 NPE。
public class TreeNode {
Integer val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(Integer val) {
this.val = val;
}
TreeNode(Integer val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public List<Integer> postorderTraversal() {
List<Integer> l = new ArrayList<>();
if (this == null) return l;
printPostOrder(this, l);
return l;
}
private void printPostOrder(TreeNode c, List<Integer> l) {
if (c.left != null && c.left.val != null) {
printPostOrder(c.left, l);
}
if (c.right != null) {
printPostOrder(c.right, l);
}
l.add(c.val);
}
public static 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;
}
}
public static void main(String[] args) {
Integer[] integers = new Integer[]{1, null, 2, 3};
TreeNode treeNode = TreeNode.fromArray(integers);
List<Integer> list = treeNode.postorderTraversal();
list.forEach(System.out::println);
}
我的 TreeNode 类似乎对我来说工作得很好：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class TreeNode {
public Integer val;
public TreeNode left;
public TreeNode right;
public TreeNode(Integer val) {
this.val = val;
}
public static TreeNode fromArray(Integer[] input) {
Integer[] parsedInput = parseInput(input);
return createTreeNode(parsedInput, 1);
}
private static Integer[] parseInput(Integer[] input) {
Map<Integer, List<Integer>> store = new HashMap<>();
int level = 1;
for (int i = 0; i < input.length; ) {
List<Integer> currValues = store.getOrDefault(level, new ArrayList<>());
if (level > 1) {
List<Integer> prevValues = store.get(level / 2);
int j = 0;
while (j < prevValues.size() && prevValues.get(j) == null) {
j++;
currValues.add(null);
currValues.add(null);
}
}
while (currValues.size() < level && i < input.length) {
currValues.add(input[i]);
i++;
}
store.put(level, currValues);
level *= 2;
}
List<Integer> res = new ArrayList<>();
int count = 0;
for (int i = 1; i < level; i *= 2) {
res.addAll(store.get(i));
count += i;
while (res.size() < count) {
res.add(null);
}
}
return res.toArray(new Integer[0]);
}
private static TreeNode createTreeNode(Integer[] input, int index) {
if (index <= input.length) {
Integer value = input[index - 1];
if (value != null) {
TreeNode treeNode = new TreeNode(value);
treeNode.left = createTreeNode(input, index * 2);
treeNode.right = createTreeNode(input, index * 2 + 1);
return treeNode;
}
}
return null;
}
}
使用示例：
TreeNode.fromArray(new Integer[]{8,3,10,1,6,null,14,null,null,4,7,13});