从数组创建 BST

Question

我需要通过以下（奇怪的）方式创建二叉搜索树：

给我一个数组（A[n]）。 A[1] 成为树的根。

• 然后，我将 A[1]+A[2] 插入到根的左子树（subtree1，下面使用），并将 A[1]-A[2] 插入到根的右子树（subtree2） ）

• 我将 A[1]+A[2]+A[3] 插入到 subtree1 (subtree3) 的左子树，将 A[1]+A[2]-A[3] 插入到 subtree1 的右子树 ( subtree4)。

• 然后，我将 A[1]-A[2]+A[3] 插入到 subtree2 (subtree5) 的左子树，将 A[1]-A[2]-A[3] 插入到 subtree2 (subtree5) 的右子树subtree2 (subtree6)。

• 我对 subtree3、subtree4、subtree5、subtree6 重复，直到到达数组的末尾。

因此，基本上，数组的第一个元素成为树的根，然后向下移动：每个左子树的值是其父级加上数组的下一个元素的和，每个右子树的值是它的父元素和数组中下一个元素的父元素。

我知道我需要使用递归的概念，但以修改的方式。在这里输入我的问题并试图向除了我的大脑之外的其他人解释它实际上让我以一种给我一些想法尝试的方式形成它，但我可以看到我正在处理的问题是一个常见的问题，所以也许你可以给给我一些关于如何使用递归来构建树的指导。

环顾其他问题和讨论，我了解到有一项政策禁止提出完整的解决方案，因此我想明确表示我不是在寻求解决方案，而是在寻求指导。如果有人想看一下，我可以向您展示我已经完成的工作。

Answer 1

进行递归的方法是始终假设您手头已经有一个工作函数。那么让我们看看[使用 Java 语法]...

Tree buildTree(int currentSum, int[] array, int index, boolean sign);

假设可行。那么你需要在索引 i 处构建一棵树吗？

// current value to look at at this level
int curValue = array[index];
// depending on sign, it may be negative
if (!sign) { 
  curValue *= -1;
}
// add it to the running total
int nodeValue = currentSum + curValue;
Node nd = new Node(nodeValue);

nd.left = buildTree(nodeValue, array, index + 1, true);
nd.right = buildTree(nodeValue, array, index + 1, false);

基本上就是这样。您需要处理边缘情况：index = array.length、创建第一个节点等