二叉树的祖先

问题描述

必须说问题1是否是二叉树中问题2的祖先

it must say if question1 is an ancestor of question2 in a binary tree

#include <iostream>
#include <string>
using namespace std;

struct node
{
    string question;
    node *left, *right;


};



node *newNode(string m_question)
{
    node *temp=new node;
    temp->question=m_question;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}





bool is_ancestor(node* start, string question1, string question2)
{
    node *root;

    if(start==NULL){return false;}
    if(start->question==question1)
    {

        while(start!=NULL)
        {
            if(start->left->question==question2)
            {
                return true;

            }
            else{
                start=start->left;
            }

        }
        while(root!=NULL)
        {
            if(root->right->question==question2)
            {
                return true;
            }
            else{
                root=root->right;
            }
        }
    }
    else{
        is_ancestor(start->left, question1, question2);
        is_ancestor(start->right, question1, question2);
    }
}
int main() {

    node *start = newNode("Bob");

    node *root=start;

    string question1="Jack";
    string question2="Linda";

    start->left = newNode("Jack");
    start->right = newNode("Maria");



    start->left->left = newNode("Linda");

    cout<<is_ancestor(start, question1, question2)<<endl;
}

我尝试了什么：



我试图通过指向第一个节点（start和root）的两个节点来解决。当我调试时，我看到在返回true语句后它进入else块并递归遍历二叉树。为什么会这样？

What I have tried:

I have tried to solve by two nodes pointing to the first node(start and root). when I debug, I see that after return true statement it goes inside else block and recursively traverses binary tree again. why is it like that?

推荐答案

这篇关于二叉树的祖先的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！