如何从数组表示构建不完全二叉树

Question

如果输入是数组，则null表示没有节点。

输入：

[1, 2, 3, null, 5, null, 7]

请假设我已经检查了输入。

对于每个array[i]，其父项array[i / 2]不会是null（递归地，所以 root 不能是null）。

如何构建具有这种逻辑关系的树：

   1
 /    \
2      3
 \      \ 
  5      7

每个节点都应该由一个TreeNode对象表示：

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

我在这里找到了一个博客，其中构建了一个完整的树

但是如果树如上所述不完整，如何整齐有效地完成它？

测试数据：

[输入数组]

[-64,12,18,-4,-53,null,76,null,-51,null,null,-93,3,null,-31,47,null,3,53,-81,33,4,null,-51,-44,-60,11,null,null,null,null,78,null,-35,-64,26,-81,-31,27,60,74,null,null,8,-38,47,12,-24,null,-59,-49,-11,-51,67,null,null,null,null,null,null,null,-67,null,-37,-19,10,-55,72,null,null,null,-70,17,-4,null,null,null,null,null,null,null,3,80,44,-88,-91,null,48,-90,-30,null,null,90,-34,37,null,null,73,-38,-31,-85,-31,-96,null,null,-18,67,34,72,null,-17,-77,null,56,-65,-88,-53,null,null,null,-33,86,null,81,-42,null,null,98,-40,70,-26,24,null,null,null,null,92,72,-27,null,null,null,null,null,null,-67,null,null,null,null,null,null,null,-54,-66,-36,null,-72,null,null,43,null,null,null,-92,-1,-98,null,null,null,null,null,null,null,39,-84,null,null,null,null,null,null,null,null,null,null,null,null,null,-93,null,null,null,98]

Answer 1

我认为这个例子可以解释你的想法。

array : [5,4,8,11,null,17,4,7,null,null,null,5]
Tree : 

                      5
                     /  \
                    4    8
                   /    / \
                  11   17  4
                 /        /
                7        5

以上所有答案都将输入数组视为一棵完整的树。所以 left.child=2 idx+1 , right.child = 2 idx+2 但实际上是错误的。因为那些

array : [5,4,8,11,null,17,4,7,null,null,null,5]
Tree : 

                      5
                     /  \
                    4    8
                   /    / \
                  11   17  4
                 /        /
                7        5

是不同的

这是我的解决方案

[5,4,8,11,null,17,4,7,null,null,null,5]
[5,4,8,11,null,17,4,7,null,null,null,null,null,5,null]

Answer 2

将二叉树实现为数组时，有助于清楚地了解两种表示如何相互反映，并查看强调关系的数学结构。

如果我们考虑 0 索引数组，数学关系可以这样分解，

• 根节点的索引为 0

对于i:th节点（i是数组索引），我们有（验证）

• 节点的左孩子有索引 2i + 1
• 节点的右孩子有索引 2(i + 1)
• 节点的父节点具有索引 floor((i-1)/2)

所以，对于二叉树

如果我们让-表示null, 表示为

[0:a, 1:b, 2:c, 3:d, 4:e, 5:-, 6:-, 7:-, 8:-, 9:g, 10:-, 11:-, 12:-, 13:-, 14:-]

所以现在要从数组创建 OO 表示，您只需应用这些索引规则。所以，既然你知道根节点是a那么我们得到它的孩子：

• 剩下： 2*0 + 1 = 1 => b
• 对： 2*(0 + 1) = 2 => c

伪代码

for (int idx = 0; 2*(idx + 1) < len(arr); idx++) {
    if (arr[idx] == null) {
        // There is no node to add for this index
        continue;
    }

    TreeNode t = null;

    if (idx == 0) {
        // Root node case
        t = TreeNode(val: arr[idx]);
        binary_tree.add(id: idx, node: t);
    }

    // We do not know if these exist yet
    int left_idx = 2*idx + 1; 
    int right_idx = 2*(idx + 1);

    if (left_idx >= len(arr)) {
        // left_idx is out of bounds with respect to the array, 
        // and by extension so would the right node be
        continue;
    }

    TreeNode left = null;
    TreeNode right = null;

    if (arr[left_idx] != null) {
        // This node has never been encountered before
        // and it is non-null so it must be created.
        //
        // Since we know we have a root node then there is
        // no need to check if the tree already contains this
        // node, it simply is not possible. Ditto for the right
        // node.
        left = TreeNode(val: arr[left_idx]);
        binary_tree.add(id: left_idx, node: left);
    }

    if (right_idx >= len(arr)) {
        // There cannot be a right child
        continue;
    }

    if (arr[right_idx] != null) {
        // This node has never been encountered before
        // and it is non-null so it must be created.
        right = TreeNode(val: arr[right_idx]);
        binary_tree.add(id: right_idx, right);
    }

    // It does not matter if left or right is null
    t.set_left(left)
    t.set_right(right)    
}