編程算法 - 二叉樹的最低公共祖先 代碼(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