1、二叉树是个搜索二叉树
2、二叉树带有指向 parent 的指针
可转换成两个链表的相交节点
3、普通二叉树
保存从根节点分别到这两个节点的路径到 list1 和 list2 中
从 list1 和 list2 中找第一个不相等的节点即为最近公共祖先节点
- template<class T>
- BinaryTreeNode<T>* BinaryTree<T>::lastCommnParent(BinaryTreeNode<T>*& node1, BinaryTreeNode<T>*& node2)
- {
- if (_root == NULL || node1 == NULL || node2 == NULL)return NULL;
- std::list<BinaryTreeNode<T>*> list1, list2;
- GetNodePath(node1, list1);
- GetNodePath(node2, list2);
- BinaryTreeNode<T>* ret = _root;
- std::list<BinaryTreeNode<T>*>::iterator it1 = list1.begin();
- std::list<BinaryTreeNode<T>*>::iterator it2 = list2.begin();
- while (it1 != list1.end() && it2 != list2.end()){
- if (*it1 == *it2){
- ret = *it1;
- ++it1, ++it2;
- }
- else
- break;
- }
- return ret;
- }
- template<class T>
- void BinaryTree<T>::GetNodePath(BinaryTreeNode<T>*& node, std::list<BinaryTreeNode<T>*>& listpath)
- {
- if (node == NULL)return;
- BinaryTreeNode<T>* cur = _root;
- BinaryTreeNode<T>* prev = cur;
- listpath.push_back(cur);
- cur = cur->_leftchild;
- while (cur != NULL || !listpath.empty()){
- while (cur != NULL){
- listpath.push_back(cur);
- if (cur == node)return;
- cur = cur->_leftchild;
- prev = cur;
- }
- BinaryTreeNode<T>* top = listpath.back();
- if (top->_rightchild == NULL || top->_rightchild == prev){
- prev = top;
- listpath.pop_back();
- }
- else
- cur = top->_rightchild;
- }
- }
《完》
来源: http://www.bubuko.com/infodetail-1978507.html