从值序列构造二叉树

Question

如何根据值序列构建二叉树。

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1

Input with null: [1,2,3,null,5,6,7]

       1
     /   \
    2     3
  /  \   /  \
null  5  6   7

注意：树不是二叉搜索树。节点按预定顺序插入（根、左、右）。首先从左到右填充子节点。一旦水平被填满，去一个新的水平。我的直觉是保留对父节点的引用。

public class TreeNode {
    public int value;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        value = x;
    }
}

public static TreeNode createTree(List<Integer> values) {
   // ???
   // return the root node
}

我觉得问这个很蠢

PS：我想知道树是如何根据输入 https://leetcode.com/problems/sum-root-to-leaf-numbers/

构建的

PS2 : Berto99给出了递归方式的草稿。想知道迭代方式（需要保留父节点的引用）

Answer 1

从大量的灵感中汲取灵感：

public static TreeNode createTree(List<Integer> values, int index) {
   TreeNode tree = new TreeNode(values[index]);
   if(index * 2 < list.size())
       tree.left = createTree(values, index * 2);
   if(index * 2 + 1 < list.size())
       tree.right = createTree(values, index * 2 + 1);
   return tree;
}

请记住，这适用于从 1 开始的索引，如果您想要从 1 开始的版本，您应该使用

public static TreeNode createTree(List<Integer> values, int index) {
   TreeNode tree = new TreeNode(values[index-1]); //   <<--- changed here
   if(index * 2 < list.size())
       tree.left = createTree(values, index * 2);
   if(index * 2 + 1 < list.size())
       tree.right = createTree(values, index * 2 + 1);
   return tree;
}

逻辑非常简单，给定一个数组，root 是第一个元素，左子元素是 pos*2，右子元素是 pos*2 + 1（同样，第一个 = 1，不是 0)

Answer 2

@Berto99 给出了主要思想

用输入[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]

可视化树

             0
        /          \
      1             2
    /   \         /    \
  3       4      5       6 
 / \    /  \    /  \    /  \
7   8  9   10  11  12  13  14

Substitute the value 3 by index then you can infer the recurrence for left and right node.
node(3).left = 7 = 2 * index + 1
node(3).right = 8 = 2 * index + 2

完整的微调代码为

    public static TreeNode createTree(List<Integer> values) {
        if (values == null || values.size() == 0) return null;
        TreeNode root = createTree(values, 0);
        return root;
    }

    private static TreeNode createTree(List<Integer> values, int index) {
        if (index >= values.size()) return null;

        Integer value = values.get(index);
        if (value == null) return null;

        TreeNode tree = new TreeNode(value);

        // tree(index).left = 2 * index + 1
        tree.left = createTree(values, index * 2 + 1);

        // tree(index).right = 2 * index + 2
        tree.right = createTree(values, index * 2 + 2);

        return tree;
    }

从值序列构造二叉树

Construct a binary tree from a sequence of values

java

binary-tree

insert