从有序和预序重建二叉树 [英] reconstructing binary tree from inorder and preorder

问题描述

我正在尝试从以下位置构建二叉树:

I am trying to build a binary tree from:

•预订: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

• Preorder: A B C D E F G H I J K L M
• Inorder: C E D F B A H J I K G M L

我几乎肯定树的左半部分是正确的，但是右半部分似乎并不正确.

I am almost positive the left half of the tree is correct, but the right half just does not seem right.

任何人都可以看到我的问题在哪里吗?

Can anyone see if they can figure out where my issue is?

我知道预订单是Parent，Left，Right 顺序是左，父，右

I know preorder is Parent, Left, Right and that inorder is Left, Parent, Right

我需要怎么做才能确保这棵树是正确的?

What do I need to do to make sure this tree is correct?

推荐答案

您可以将以下算法应用于预排序和有序遍历.生成的树将始终有效且唯一.

You can apply following algorithm with your preorder and inorder traversal. The resulting tree will always be valid and unique.

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

如果您难以理解，我会添加解释.

I will add explanation if you feel difficulties to understand.

应用我在给定的有序和预序列上提到的算法，结果树如下-

Applying above algorithm I mentioned on the given inorder and preorder sequences, The resulting tree is given below -

这篇关于从有序和预序重建二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！