对于给定中序和前序遍历的二叉树，如何推导出此公式的证明以正确 child ？

Question

我正在 leetcode 上查看这个 question。给定两个数组，中序和前序，您需要构造一棵二叉树。我得到了问题的一般解决方案。

前序遍历遍历根、左、右，所以左child就是当前的前序节点索引+1。从这个值，你就可以知道树的左边有多少个节点使用中序数组。在答案中，用于获得正确child的公式是“preStart + inIndex - inStart + 1”。

我不想死记硬背公式，所以我想知道是否有这方面的证明？我浏览了那里的讨论板，但我仍然缺少 link。

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

对于给定中序和前序遍历的二叉树，如何推导出此公式的证明以正确 child ？

How to derive the proof of this formula for getting right child for a binary tree given inorder and preorder traversals?

algorithm

binary-tree

tree-traversal

inorder

preorder

仅限Python

C++