首页 / 操作系统 / Linux / 编程算法 - 二叉树的最低公共祖先 代码（C）

二叉树的最低公共祖先 代码（C） 

二叉树的最低公共祖先（lowest common ancestor）, 首先先序遍历找到两个结点的路径, 然后根据链表路径找到最低的公共祖先.代码:/*
 * main.cpp
 *
 *  Created on: 2014.6.12
 *      Author: Spike
 *//*eclipse cdt, gcc 4.8.1*/#include <iostream>
#include <list>
#include <queue>using namespace std;struct BinaryTreeNode {
 BinaryTreeNode（int _value） {
  value = _value;
  left = NULL;
  right = NULL;
 } int value;
 BinaryTreeNode* left;
 BinaryTreeNode* right;
};void printTree （BinaryTreeNode* tree）
{
 BinaryTreeNode* node = tree;
 std::queue<BinaryTreeNode*> temp1;
 std::queue<BinaryTreeNode*> temp2; temp1.push（node）; while （！temp1.empty（））
 {
  node = temp1.front（）;
  if （node->left ！= NULL） {
   temp2.push（node->left）;
  }  if （node->right ！= NULL） {
   temp2.push（node->right）;
  }  temp1.pop（）;  std::cout << node->value  << " ";  if （temp1.empty（））
  {
   std::cout << std::endl;
   temp1 = temp2;
   std::queue<BinaryTreeNode*> empty;
   std::swap（temp2, empty）;
  }
 }
}BinaryTreeNode* buildTree （void）
{
 BinaryTreeNode* root = new BinaryTreeNode（1）;
 BinaryTreeNode* node2 = new BinaryTreeNode（2）;
 BinaryTreeNode* node3 = new BinaryTreeNode（3）;
 BinaryTreeNode* node4 = new BinaryTreeNode（4）;
 BinaryTreeNode* node5 = new BinaryTreeNode（5）;
 BinaryTreeNode* node6 = new BinaryTreeNode（6）;
 BinaryTreeNode* node7 = new BinaryTreeNode（7）;
 BinaryTreeNode* node8 = new BinaryTreeNode（8）;
 BinaryTreeNode* node9 = new BinaryTreeNode（9）;
 BinaryTreeNode* node10 = new BinaryTreeNode（10）; root->left = node2;
 root->right = node3; node2->left = node4;
 node2->right = node5; node4->left = node6;
 node4->right = node7; node5->left = node8;
 node5->right = node9; node9->left = node10; return root;
}bool GetNodePath（BinaryTreeNode* root, int v, vector<BinaryTreeNode*>& path） {
 if （root->value == v）
  return true;
 path.push_back（root）;
 bool found = false;
 if （root->left ！= NULL && ！found）
  found = GetNodePath（root->left, v, path）;
 if （root->right ！= NULL && ！found）
  found = GetNodePath（root->right, v, path）;
 if （！found）
  path.pop_back（）;
 return found;
}BinaryTreeNode* GetLastCommonNode （
  const vector<BinaryTreeNode*>& path1, const vector<BinaryTreeNode*>& path2）
{
 vector<BinaryTreeNode*>::const_iterator it1 = path1.begin（）;
 vector<BinaryTreeNode*>::const_iterator it2 = path2.begin（）;
 BinaryTreeNode* pLast = NULL;
 while （it1 ！= path1.end（） && it2 ！= path2.end（）） {
  if （（*it1）->value == （*it2）->value）
   pLast = *it1;
  it1++;
  it2++;
 }
 return pLast;
}BinaryTreeNode* GetLastCommonParent（BinaryTreeNode* root, int v1, int v2）
{
 if （root == NULL）
  return NULL;
 vector<BinaryTreeNode*> path1;
 GetNodePath（root, v1, path1）;
 vector<BinaryTreeNode*> path2;
 GetNodePath（root, v2, path2）; return GetLastCommonNode（path1, path2）;
}int main （void）
{
 BinaryTreeNode* root = buildTree（）;
 int v1 = 6;
 int v2 = 10;
 BinaryTreeNode* common = GetLastCommonParent（root, v1, v2）;
 cout << "common node : " << common->value << endl;
 return 0;
}输出:common node : 2本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-10/107630.htm