二叉树的最低公共祖先 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

二叉树的最低公共祖先(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