algorithm - 从中序和前序重建二叉树

Question

我正在尝试从以下内容构建二叉树:

• 预购:A B C D E F G H I J K L M
• 顺序:C E D F B A H J I K G M L

我几乎肯定树的左半边是正确的，但右半边似乎不对。

谁能看看他们是否能找出我的问题出在哪里？

我知道预序是 Parent, Left, Right那个顺序是左，父，右

我需要做什么来确保这棵树是正确的？

Answer 1

您可以在先序和中序遍历中应用以下算法。生成的树将始终有效且唯一。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

TreeNode *treeBuilder(vector<int> &preorder, vector<int> &inorder, int start, int end, int indx) {
    if(start > end) return nullptr;

    TreeNode *root = new TreeNode(preorder[indx]);
    int rootPosition;    
    for(int i = start; i <= end; ++i) {
        if(inorder[i] == root->val) {
            rootPosition = i;
            break;
        }
    }
    root->left = treeBuilder(preorder, inorder, start, rootPosition - 1, indx + 1);
    root->right = treeBuilder(preorder, inorder, rootPosition + 1, end, indx + 1 + rootPosition - start);
    return root;
}

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    if(preorder.size() == 0) return nullptr;
    return treeBuilder(preorder, inorder, 0, inorder.size() - 1, 0);
}

如果你觉得难以理解，我会添加解释。

编辑

在给定的中序和前序序列上应用我提到的上述算法，结果树如下所示 -