LCA 最近公共祖先

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    struct node *left;
    struct node *right;
    int data;
} node;

void travel(node * r,node*a,node *b,int * global)
{
    if(r==NULL|| *global>=3)return;

    int i=*global;
    if(r==a||r==b) (*global)++;

    if(r==a&&r==b) (*global)=2;

//    printf("%d\n",r->data);

//


    travel(r->left,a,b,global);
    travel(r->right,a,b,global);
    if(i==0 && *global==2) {
        (*global)++;
        printf("LCA is %d\n",r->data);
    }

//    printf("%d\n",r->data);


}

int main()
{
    node * root=(node*)malloc(sizeof(node));
    root->data=0;

    node * root1=(node*)malloc(sizeof(node));
    root1->data=1;

    node * root2=(node*)malloc(sizeof(node));
    root2->data=2;
    
    node * root3=(node*)malloc(sizeof(node));
    root3->data=3;
    
    
    node * root4=(node*)malloc(sizeof(node));
    root4->data=4;
    
    node * root5=(node*)malloc(sizeof(node));
    root5->data=5;
    
    node * root6=(node*)malloc(sizeof(node));
    root6->data=6;
    
    node * root7=(node*)malloc(sizeof(node));
    root7->data=7;

    node * root8=(node*)malloc(sizeof(node));
    root8->data=8;
    
    node * root9=(node*)malloc(sizeof(node));
    root9->data=9;

    root->left=root1;
    root->right=root2;

    root1->left=root3;
    root1->right=NULL;

    root3->left=NULL;
    root3->right=root4;

    root4->left=root8;
    root4->right=NULL;

    root8->left=root8->right=NULL;

    root2->left=NULL;
    root2->right=root5;

    root5->left=root6;
    root5->right=root7;

    root6->left=root6->right=NULL;

    root7->left=root9;
    root7->right=NULL;

    root9->left=root9->right=NULL;

    int g=0;

    travel(root,root3,root2,&g);

    g=0;
    travel(root,root1,root8,&g);

    g=0;
    travel(root,root6,root9,&g);



    return 0;
}