给定非空二叉树的中根序列和后根序列，请编写程序创建该二叉树，计算其高度和先根...

申谭

#include <iostream>
#include <cstring>
#include<math.h>
using namespace std;

struct node {
    char data;
    node* left;
    node* right;
};

typedef node* tree;

int find_(char* inorder, int size, char data) {
    for (int i = 0; i < size; i++) {
        if (inorder[i] == data)
            return i;
    }
    return -1;
}

node* buildtree(char* postorder, char* inorder, int n) {
    if (n <= 0)
        return NULL;
    char tdata = postorder[n - 1];
    int k = find_(inorder, n, tdata);
    if(k==-1)
    {
        return NULL;
    }
    node* root = new node;
    root->data = tdata;
    root->left = buildtree(&postorder[0], &inorder[0], k);
    root->right = buildtree(&postorder[k], &inorder[k+1], n - k - 1);
    return root;
}

int get_height(tree t) {
    if (t == NULL)
        return -1;
   
    int d1 = get_height(t->left);
    int d2 = get_height(t->right);
    return max(d1, d2) + 1;
}

void Preorder(tree t) {
    if (t == NULL)
        return;
   
    cout << t->data;
    Preorder(t->left);
    Preorder(t->right);
}

int main() {
    char postorder[10000];
    char inorder[10000];
    while (scanf("%s", postorder) != EOF && scanf("%s", inorder) != EOF) {
        int n = strlen(inorder);
        tree root = buildtree(postorder, inorder, n);
        int height = get_height(root);
        if(root==NULL) cout<<"INVALID"<<endl;
        else
        {
        cout << height << endl;
        Preorder(root);
        cout << endl;
        }
    }
    return 0;
}感觉在递归的时候如果k==-1就要返回上一级而不是直接结束函数，导致一些不合法的输入，还会输出一些字符，该如何修改

isdkz

你需要在递归的时候，当  k==-1  时返回上一级，而不是直接结束函数。这样可以避免输出一些不合法的字符。你可以修改  buildtree  函数中的条件判断，如下所示：

1. node* buildtree(char* postorder, char* inorder, int n) {
   
2.     if (n <= 0)
   
3.         return NULL;
   
4.     char tdata = postorder[n - 1];
   
5.     int k = find_(inorder, n, tdata);
   
6.     if(k==-1)
   
7.     {
   
8.         return NULL;
   
9.     }
   
10.     node* root = new node;
    
11.     root->data = tdata;
    
12.     root->left = buildtree(&postorder[0], &inorder[0], k);
    
13.     if(root->left == NULL) // 如果左子树为空，返回上一级
    
14.     {
    
15.         delete root;
    
16.         return NULL;
    
17.     }
    
18.     root->right = buildtree(&postorder[k], &inorder[k+1], n - k - 1);
    
19.     if(root->right == NULL) // 如果右子树为空，返回上一级
    
20.     {
    
21.         delete root;
    
22.         return NULL;
    
23.     }
    
24.     return root;
    
25. }
    

复制代码

通过在递归的过程中加入对左右子树是否为空的判断，可以避免输出不合法的字符。

Mike_python小

在当前的代码中，当 k == -1 时，会直接返回 NULL，导致递归函数结束。为了在遇到不合法的输入时返回上一级，你可以在递归函数中添加一个判断条件，如果 k == -1 则返回上一级。

以下是修改后的代码片段：

2. node* buildtree(char* postorder, char* inorder, int n) {
3.     if (n <= 0)
4.         return NULL;
5.    
6.     char tdata = postorder[n - 1];
7.     int k = find_(inorder, n, tdata);
8.     if(k == -1) {
9.         return NULL;
10.     }
11.    
12.     node* root = new node;
13.     root->data = tdata;
14.     root->left = buildtree(&postorder[0], &inorder[0], k);
15.     if (root->left == NULL) {
16.         // 非法输入，返回上一级
17.         delete root;
18.         return NULL;
19.     }
20.     root->right = buildtree(&postorder[k], &inorder[k+1], n - k - 1);
21.     if (root->right == NULL) {
22.         // 非法输入，返回上一级
23.         delete root->left;
24.         delete root;
25.         return NULL;
26.     }
27.    
28.     return root;
29. }

复制代码

请注意，当发现左子树或右子树为空时，我们将删除已创建的节点并返回 NULL，以确保整个树的结构正确。

希望这可以解决你的问题。如果还有其他疑问，请随时提问。

申谭

Mike_python小 发表于 2023-11-20 19:25
在当前的代码中，当 k == -1 时，会直接返回 NULL，导致递归函数结束。为了在遇到不合法的输入时返回上一级 ...

但是走到左分支左后不是一定要指向NULL
CBEDFAGH
CEFDBHGA
我说的错误是类似于这种然后输出INVALID
现在代码输出2
HFDGA

LazyBreeze

申谭 发表于 2023-11-20 19:44
但是走到左分支左后不是一定要指向NULL
CBEDFAGH
CEFDBHGA

我也在思考这个问题，楼主有想法了吗，抛掷异常更容易出现问题