将整数数组转换为二叉树

Question

我已经可以在 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}足够清晰，可以定义像上面这样的树。

避免输入数组中定义的冗余空值有什么好主意吗？

Answer 1

这是一个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};

Answer 2

如果你按顺序阅读这棵树，你会发现1, -, 2, 3, -。index*2只需使用相同的顺序构造树，而不是在和 处查找字符串index*2+1，而是从左到右查找。（如果您愿意，您可以丢弃最后的空值）。

对于更“复杂”的示例：

       1
     /   \
   2       3
    \     / \
     4   5   6
          7   8

1, 2, -, 4, 3, 5, -, 7, 6, -, 8