对于给定序和预序遍历的二叉树，如何推导出这个公式的证明

Question

我在leetcode上看这个问题。给定两个数组，有序和预序，您需要构造一个二叉树。我得到了这个问题的大致答案。

预购遍历访问根节点、左节点和右节点，所以左边的子节点将是当前预购节点索引+1。根据该值，您可以使用有序数组知道树左侧有多少节点。在答案中，用来找到合适孩子的公式是"；preStart+inIndex-inStart+1"；。

我不想记住这个公式，所以我想知道是否有证据？我浏览了那里的讨论板，但仍然缺少一个链接。

Answer 1

仅适用于Python

• 在Python中，我们也可以使用pop(0)来解决这个问题，尽管这是低效的(它会通过(。

• 对于低效率，我们可能会将deque()与popleft()一起使用，但不能在LeetCode上使用，因为我们无法控制树。

class Solution:
def buildTree(self, preorder, inorder):
if inorder:
index = inorder.index(preorder.pop(0))
root = TreeNode(inorder[index])
root.left = self.buildTree(preorder, inorder[:index])
root.right = self.buildTree(preorder, inorder[index + 1:])
return root

---

对于Java和C++，这会有点不同，就像你说的那样(没有证据(，但也许这篇文章会有点帮助：

public class Solution {
public static final TreeNode buildTree(
final int[] preorder,
final int[] inorder
) {
return traverse(0, 0, inorder.length - 1, preorder, inorder);
}
private static final TreeNode traverse(
final int preStart,
final int inStart,
final int atEnd,
final int[] preorder,
final int[] inorder
) {
if (preStart > preorder.length - 1 || inStart > atEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int inorderIndex = 0;
for (int i = inStart; i <= atEnd; i++)
if (inorder[i] == root.val) {
inorderIndex = i;
}
root.left = traverse(preStart + 1, inStart, inorderIndex - 1, preorder, inorder);
root.right = traverse(preStart + inorderIndex - inStart + 1, inorderIndex + 1, atEnd, preorder, inorder);
return root;
}
}

C++

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
#include <unordered_map>
using ValueType = int;
static const struct Solution {
TreeNode* buildTree(
std::vector<ValueType>& preorder,
std::vector<ValueType>& inorder
) {
std::unordered_map<ValueType, ValueType> inorder_indices;
for (ValueType index = 0; index < std::size(inorder); ++index) {
inorder_indices[inorder[index]] = index;
}
return build(preorder, inorder, inorder_indices, 0, 0, std::size(inorder) - 1);
}
private:
TreeNode* build(
std::vector<ValueType>& preorder,
std::vector<ValueType>& inorder,
std::unordered_map<ValueType, ValueType>& inorder_indices,
ValueType pre_start,
ValueType in_start,
ValueType in_end
) {
if (pre_start >= std::size(preorder) || in_start > in_end) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[pre_start]);
ValueType pre_index = inorder_indices[preorder[pre_start]];
root->left = build(preorder, inorder, inorder_indices, pre_start + 1, in_start, pre_index - 1);
root->right = build(preorder, inorder, inorder_indices, pre_start + 1 + pre_index - in_start, pre_index + 1, in_end);
return root;
}
};