java 将整数数组转换为二叉树
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/26891747/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
convert integer array into a binary tree
提问by rekinyz
I can already convert an array into a binary tree using following algorithm in java:
我已经可以在 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,null,2,null,null,3} 时，我得到以下树：
1
\
2
/
3
however I think the input {1,null,2,3}is clear enough to define a tree like above.
但是我认为输入{1,null,2,3}足够清晰，可以定义像上面这样的树。
Any good idea to avoid the redundant nullsdefined in the input array?
避免输入数组中定义的冗余空值有什么好主意吗？
回答by irisha_murrr
Here is a java-monster and it solves the task with the possibility of debugging
这是一个 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);
}
}
more interesing example is
更有趣的例子是
Integer[] tree = new Integer[]{5,4,8,11,null,13,4,7,2,null,null,null,1};
回答by Yves Daoust
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*2and index*2+1, but left to right. (You can discard the final nulls if you like).
如果您按顺序阅读这棵树，您会发现1, -, 2, 3, -. 只需使用相同的顺序构建树，而不是在index*2and处查找字符串index*2+1，而是从左到右查找。（如果您愿意，您可以丢弃最终的空值）。
For a more "complex" example:
对于更“复杂”的示例：
1
/ \
2 3
\ / \
4 5 6
7 8
1, 2, -, 4, 3, 5, -, 7, 6, -, 8
