144-13-526互联

给定结点p,q，在二叉树中找到两结点最近的祖宗结点

1. 首先，检查当前节点T是否为空，或者是否等于节点p或节点q。如果是，直接返回当前节点T，表示找到了p或q节点，或者已经遍历到
叶子节点。
2. 如果当前节点T不满足上述条件，则递归地处理左子树和右子树。
3. 在左子树中递归调用`ANCESTOR`函数，将返回结果赋给左子树的最近公共祖先节点指针left。
4. 在右子树中递归调用`ANCESTOR`函数，将返回结果赋给右子树的最近公共祖先节点指针right。
5. 根据left和right的值进行判断：
   - 如果left和right都不为空，说明节点p和节点q分别位于当前节点T的左右子树中，当前节点T即为最近公共祖先节点，直接返回T。
   - 如果只有left不为空，说明节点p和节点q都在左子树中，返回left。
   - 如果只有right不为空，说明节点p和节点q都在右子树中，返回right。

通过递归的方式，可以从二叉树的根节点开始，逐层向下查找节点p和节点q的最近公共祖先节点。在每一层递归中，根据左子树和右子树的返回结果，确定当前节点的最近公共祖先节点。

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

#define MaxSize 100

typedef struct node{
    int data;
    struct node *lchild,*rchild;
}TreeNode,*Tree;

void CreateTree(Tree &T)
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;
    }
    else
    {
        T=(TreeNode*)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点:",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点:",x);
        CreateTree(T->rchild);
    }
}

TreeNode* ANCESTOR(Tree T,TreeNode* p,TreeNode* q)
{
    if(T==NULL || T==p || T==q)
        return T;
    TreeNode *left=ANCESTOR(T->lchild,p,q);
    TreeNode *right=ANCESTOR(T->rchild,p,q);
    
    if(left&&right)
        return T;
    else if(left)
        return left;
    else
        return right;
}

int main()
{
    Tree T;
    CreateTree(T);
    
    //p,q结点位于根结点左右 
    TreeNode *p=T->lchild->lchild->rchild;
    TreeNode *q=T->rchild->lchild->rchild;
    
    //    p,q结点位于根结点左侧
//    TreeNode *p=T->lchild->lchild->lchild;
//    TreeNode *q=T->lchild->rchild->lchild; 
    
    //p,q结点位于根结点右侧 
//    TreeNode *p=T->rchild->rchild->lchild;
//    TreeNode *q=T->rchild->rchild->rchild;

    TreeNode* r=ANCESTOR(T,p,q);
    if(r)
        printf("结点p和结点q最近的祖宗结点是:%d",r->data);
    else
        printf("NO"); 
        
    return 0;
}

144

networking stanford warmup 144