二叉树建树寻找节点出错,错在哪里了.

Question

这道题目要求返回输入值a,b的公共父节点,可以用数学公式直接推导,但我想练习一下建树遍历,所以写的比较麻烦
我输出为空,请问是哪一步有问题
这是题目链接:https://www.nowcoder.com/practice/5b80ab166efa4551844657603227caeb?tpId=40&tqId=21378&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan&difficulty=3&judgeStatus=3&tags=/question-ranking

#include<vector>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

struct Node{
    int d;//数据
    struct Node* left;//左孩子
    struct Node* right;//右孩子
};

void build(Node* root,int d){//用层序序列建树
    int index=1;
    queue<Node*>t;
    t.push(root);
    while(index<=d){
        Node* temp=t.front();
        t.pop();
        temp->d=index++;
        
        Node* left=(Node*)malloc(sizeof(Node));//左孩子结点
        left->d=-1;
        left->left=left->right=NULL;//左孩子的左右孩子结点赋为空
        
        Node* right=(Node*)malloc(sizeof(Node));//右孩子结点
        right->d=-1;
        right->left=right->right=NULL;/右孩子的左右孩子结点赋为空
        
        temp->left=left;
        temp->right=right;//左右孩子赋给当前结点的左右孩子指针
        t.push(left);
        t.push(right);
    }
}

Node* findn(Node* root,int a,int b){//寻找a,b的公共父节点
    if(root->d==-1||root==NULL)//结点为空或超出a和b的最大值则返回
        return NULL;
        
    Node* left=findn(root->left,a,b);
    Node* right=findn(root->right,a,b);
    
    if(root->d!=a&&root->d!=b&&(!left)&&(!right))//如果子树及本节点不存在a,b
        return NULL;
    else if((left!=NULL||right!=NULL)&&(root->d==a||root->d==b))//如果a,b其中一个是另外一个的父节点
        return root;

    else if(left&&right)//如果a,b分别位于本结点的左右子树
        return root;
    else return (left!=NULL)?left:right;//返回左右子树非空的返回值,如果为空则返回空
}

int main(){
    int a,b;
    while(cin>>a>>b){
        Node* root=(Node*)malloc(sizeof(Node));
        build(root,max(a,b));//建树建到a和b的最大值,多余的节点赋值-1
        Node* res=findn(root,a,b);
        printf("%d\n",res->d);
    }
    return 0;
}

麻烦帮我看看,谢谢了!!

Answer 1

调试下，build 这个函数，建立二叉树的代码是否有问题