查找两个节点最近的公共祖先

查找一个普通二叉树中两个节点最近的公共祖先。 方法： 1.分别找出两个节点距离根节点的路径并保存在栈中； 2.判断两个栈的长度是否相等，如果不相等，就pop（）掉size（）值较大的一个直到两个栈的长度相等。 3.分别取两个栈顶的元素，比较值是否相等，若不相等将两个栈顶元素都出栈 ，若相等，则返回栈顶元素。

using namespace std; template <class T> struct BinaryTreeNode//定义二叉树的节点 { BinaryTreeNode(const T& value) :_value(value) ,_pLeft(NULL) ,_pRight(NULL) {} T _value; BinaryTreeNode<T>* _pLeft; BinaryTreeNode<T>* _pRight; }; template<class T> class BinaryTree//定义二叉树 { typedef BinaryTreeNode<T> Node; public: BinaryTree() :_pRoot(NULL) {} private: Node* _pRoot;//根节点 };

查找二叉树最近的公共祖先：

Node* FindCommonAncestorNode(Node* first, Node* second) { if(!_pRoot || !first || !second) return NULL; return _FindCommonAncestorNode(_pRoot, first, second); } void Stack(stack<Node*>& s, Node* _pRoot, Node* first)//求两个节点距离根节点的路径 { Node* pCur = _pRoot; Node* pPre = NULL; while(pCur || !s.empty()) { while(pCur) { s.push(pCur); pCur = pCur->_pLeft; } Node* pTop = s.top(); if(pTop->_pRight == NULL || pTop->_pRight == pPre) { if(pTop->_value == first->_value) break; s.pop(); pPre = pTop; } else pCur = pTop->_pRight; } } Node* _FindCommonAncestorNode(Node* _pRoot, Node* first, Node* second) { stack<Node*> s1; stack<Node*> s2; Stack(s1, _pRoot, first); Stack(s2, _pRoot, second); while(s1.size() > s2.size()) { s1.pop(); } while(s1.size() < s2.size()) { s2.pop(); } while(s1.top() != s2.top()) { s1.pop(); s2.pop(); } return s1.top(); }