二叉树的最低公共祖先 代码(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 = http://www.mamicode.com/_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 =http://www.mamicode.com/= v)"common node : " << common->value << endl;
	return 0;
}

输出:

common node : 2