寻找二叉树中两个节点的最近的公共祖先笔试面试

题目：要求寻找二叉树中两个节点的最近的公共祖先，并将其返回。

class Node { Node * left; Node * right; Node * parent; }; /*查找p，q的最近公共祖先并将其返回。*/ Node * NearestCommonAncestor(Node * p,Node * q);

算法思想：这道题的关键在于每个节点中包含指向父节点的指针，这使得程序可以用一个简单的算法实现。首先给出p的父节点p->parent，然后将q的所有父节点依次和p->parent作比较，如果发现两个节点相等，则该节点就是最近公共祖先，直接将其返回。如果没找到相等节点，则将q的所有父节点依次和p->parent->parent作比较......直到p->parent==root。 【寻找二叉树中两个节点的最近的公共祖先】

Node * NearestCommonAncestor(Node * root,Node * p,Node * q) { Node * temp; while(p!=NULL) { p=p->parent; temp=q; while(temp!=NULL) { if(p==temp->parent) return p; temp=temp->parent; } } }