对于给定按序和按序遍历的二叉树，如何推导该公式的证明，以获得正确的子树？

Question

我在看leetcode上的这个问题。给定两个数组，按序和按序，需要构造一个二叉树。我得到了问题的通解。

预排序遍历访问根、左和右，因此左子级将是当前预排序节点索引1。根据该值，您可以使用inorder数组知道树左侧有多少个节点。在答案中，用于找到合适孩子的公式是“preStart inIndex-inStart 1”。

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

Answer 1

>

在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;
    }

}

// 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;
        }
};