时间戳

首页 > 解决方案 > 我试图找到具有给定顺序和预顺序的二叉树我正在遵循递归方法，但我得到了错误的输出

c++ - 我试图找到具有给定顺序和预顺序的二叉树我正在遵循递归方法，但我得到了错误的输出

问题描述

我正在遵循递归方法来解决问题。代码中没有语法错误

/**************** **We are given Inorder and Preorder . We have to find the Binary Tree.** ***************/

#include <iostream>
using namespace std;
#include <queue>
template<typename T>
/* Class Defination */
class BinaryTreeNode
{
public:
    T data;
    BinaryTreeNode *left;
    BinaryTreeNode *right;

    BinaryTreeNode(T data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
    
    ~BinaryTreeNode()
    {
        delete left;
        delete right;
    }
};

/* *Function to print to the Tree* */
void printTreeLevelWise(BinaryTreeNode<int> *root)
{
    if (root == NULL)
    { //Base case
        return;
    }
    queue<BinaryTreeNode<int>*> pendingNodes;
    pendingNodes.push(root);
    while (pendingNodes.size() != 0)
    {
        BinaryTreeNode<int> *front = pendingNodes.front();
        pendingNodes.pop();
        cout << front->data << ":";
        if (front->left != NULL)
        {
            cout << "L" << front->left->data;
            pendingNodes.push(front->left);
        }
        if (front->right != NULL)
        {
            cout << "R" << front->right->data;
            pendingNodes.push(front->right);
        }
        cout << endl;
    }
    
}

/* **Building the  Tree** */
BinaryTreeNode<int>* buildTreeHelper(int *in,
                                     int *pre,
                                     int inS,
                                     int inE,
                                     int preS,
                                     int preE)
{
    
    if (inS > inE)
    {
        return NULL;
    }
    
    int rootData = pre[preS];
    int rootIndex = -1;
    for (int i = inS; i <= inE; i++)
    {
        if (in[i] == rootData)
        {
            rootIndex = i;
            break;
        }
    }
    
    int lInS = inS;
    int lInE = rootIndex - 1;
    int lPreS = preS + 1;
    int lPreE = lInE - lInS + lPreS;
    int rPreS = lPreE + 1;
    int rPreE = preE;
    int rInS = rootIndex + 1;
    int rInE = inE;
    
    BinaryTreeNode<int> *root = new BinaryTreeNode<int>(rootData);
    root->left = buildTreeHelper(in, pre, lInS, lInE, lPreS, lPreE);
    root->left = buildTreeHelper(in, pre, rInS, rInE, rPreS, rPreE);
    return root;
}

BinaryTreeNode<int>* buildTree(int *in, int *pre, int size)
{
    return buildTreeHelper(in, pre, 0, size - 1, 0, size - 1);
}

int main()
{
    
    int in[] = { 4, 2, 5, 1, 8, 6, 9, 3, 7 };
    int pre[] = { 1, 2, 4, 5, 3, 6, 8, 9, 7 };
    BinaryTreeNode<int> *root = buildTree(in, pre, 9);
    printTreeLevelWise(root);
    delete root;
    return 0;
}

标签： c++data-structuresbinary-tree

解决方案

至少第二行应该是root->right = ...：

root->left = buildTreeHelper(in, pre, lInS, lInE, lPreS, lPreE);
root->left = buildTreeHelper(in, pre, rInS, rInE, rPreS, rPreE);

推荐阅读