#pragmaonce#include<iostream>usingnamespacestd;/*****************二叉树中找两个结点的最近的公共祖先结点******************/structNode{Node*left;Node*right;intvalue;Node(intv):value(v),left(NULL),right(NULL){}};

// 方法一 int count 计数

int_find_ancestor(Node*root,Node*&ancestor,constNode*a,constNode*b){if(root==NULL){return0;}intcount=0;count+=_find_ancestor(root->left,ancestor,a,b);if(root==a||root==b){count+=1;}/*if(count==2){ancestor=root;}*/count+=_find_ancestor(root->right,ancestor,a,b);if(count==2){ancestor=root;count=0;//防止返回时上面count的值还是2导致ancestor不准确被覆盖}returncount;}voidtest_find_ancestor(){//1//23//45Noden1(1);Noden2(2);Noden3(3);Noden4(4);Noden5(5);n1.left=&n2;n1.right=&n3;n2.left=&n4;n2.right=&n5;Node*ancestor=NULL;//45//_find_ancestor(&n1,ancestor,&n4,&n5);//25//_find_ancestor(&n1,ancestor,&n2,&n5);//53_find_ancestor(&n1,ancestor,&n5,&n3);}

// 方法二 bool判别

boolfind_ancestor_bool(Node*root,Node*&ancestor,constNode*a,constNode*b){if(root==NULL){returnfalse;}boolb_left=find_ancestor_bool(root->left,ancestor,a,b);boolb_right=find_ancestor_bool(root->right,ancestor,a,b);if(root==a||root==b){if(b_left||b_right){ancestor=root;}returntrue;}if(b_left&&b_right){ancestor=root;}returnb_left||b_right;}voidtest_find_ancestor_bool(){//1//23//45Noden1(1);Noden2(2);Noden3(3);Noden4(4);Noden5(5);n1.left=&n2;n1.right=&n3;n2.left=&n4;n2.right=&n5;Node*ancestor=NULL;//45//find_ancestor_bool(&n1,ancestor,&n4,&n5);//25//find_ancestor_bool(&n1,ancestor,&n2,&n5);//53//find_ancestor_bool(&n1,ancestor,&n5,&n3);//15find_ancestor_bool(&n1,ancestor,&n1,&n5);}

// 方法3 利用栈 数组或 链表 记录 找到结点的 路径 最后 遍历两个 栈（数组或链表） 找到第一次出现比相同的点的前一个 即为公共祖先

// 注意 如果当前不是 返回时 要将当前压栈的 元素弹出 栈用引用传入

// 这里以 vector 为例 方便遍历

#include<vector>voidfind_ancestor_vector_R(Node*root,vector<Node*>&va,vector<Node*>&vb,Node*a,Node*b,Node*&ancestor){if(root==NULL){return;}va.push_back(root);vb.push_back(root);find_ancestor_vector_R(root->left,va,vb,a,b,ancestor);find_ancestor_vector_R(root->right,va,vb,a,b,ancestor);if(va.back()!=a){va.pop_back();}if(vb.back()!=b){vb.pop_back();}}Node*find_ancestor_vector(Node*root,Node*a,Node*b){vector<Node*>va,vb;Node*ancestor=NULL;find_ancestor_vector_R(root,va,vb,a,b,ancestor);//找vavb的分叉点之前的点inti=0;while(i<va.size()&&i<vb.size()&&va[i]==vb[i]){ancestor=va[i];i++;}returnancestor;}voidtest_find_ancestor_vector(){//1//23//45Noden1(1);Noden2(2);Noden3(3);Noden4(4);Noden5(5);n1.left=&n2;n1.right=&n3;n2.left=&n4;n2.right=&n5;Node*ancestor=NULL;//45ancestor=find_ancestor_vector(&n1,&n4,&n5);//25ancestor=find_ancestor_vector(&n1,&n2,&n5);//53ancestor=find_ancestor_vector(&n1,&n5,&n3);//15ancestor=find_ancestor_vector(&n1,&n1,&n5);}