Geeks 一般二叉树的LCA

不是BST，那么搜索两节点的LCA就复杂点了，由于节点是无序的。

以下是两种方法，都写进一个类里面了。

当然须要反复搜索的时候。能够使用多种方法加速搜索。

#include <iostream>

#include <vector>

using namespace std;

class LCANormalTree

{

	struct Node

	{

		int key;

		Node *left, *right;

		Node(int k) : key(k) , left(NULL), right(NULL) {}

	};

	//method 1:

	bool findPath(Node *root, vector<Node *> &path, int k)

	{

		if (!root) return false;

		path.push_back(root);

		if (root->key == k) return true;

		if (findPath(root->left, path, k) ||	findPath(root->right, path, k))

			return true;

		path.pop_back();

		return false;

	}

	Node *findLCA(Node *root, int n1, int n2)

	{

		vector<Node *> pathN1, pathN2;

		if (!findPath(root, pathN1, n1) || !findPath(root, pathN2, n2))

			return NULL;

		int i = 0;

		for (; i < (int) pathN1.size() && pathN1[i] == pathN2[i]; i++);

		return pathN1[i-1];

	}

	//Method 2:

	Node *findLCAUtil(Node *root, int n1, int n2, bool &v1, bool &v2)

	{

		if (!root) return NULL;

		if (root->key == n1)

		{

			v1 = true;

			return root;

		}

		if (root->key == n2)

		{

			v2 = true;

			return root;

		}

		Node *left = findLCAUtil(root->left, n1, n2, v1, v2);

		Node *right = findLCAUtil(root->right, n1, n2, v1, v2);

		if (left && right) return root;

		return left?

left:right;

	}

	bool find(Node *root, int k)

	{

		if (!root) return false;

		if (root->key == k || find(root->left, k) || find(root->right, k))

			return true;

		return false;

	}

	Node *findLCA_2(Node *root, int n1, int n2)

	{

		bool v1 = false, v2 = false;

		Node *lca = findLCAUtil(root, n1, n2, v1, v2);

		//当两者在不同一边的时候v1&&v1，当一个为另外一个的单亲节点的时候，那么就出现后面两种情况了。

		if (v1 && v2 || v1 && find(lca, n2) || v2 && find(lca, n1))

			return lca;

		return NULL;

	}

	Node *root;

public:

	LCANormalTree()

	{

		cout<<"Algorithm 1 run\n";

		run_1();

		cout<<"\nAlgorithm 2 run\n";

		run_2();

	}

	void run_1()

	{

		root = new Node(1);

		root->left = new Node(2);

		root->right = new Node(3);

		root->left->left = new Node(4);

		root->left->right = new Node(5);

		root->right->left = new Node(6);

		root->right->right = new Node(7);

		Node *t = findLCA(root, 4, 5);

		cout << "LCA(4, 5) = " << (t? t->key : -1);

		t = findLCA(root, 4, 6);

		cout << "\nLCA(4, 6) = " << (t?

t->key : -1);

		t = findLCA(root, 3, 4);

		cout << "\nLCA(3, 4) = " << (t? t->key : -1);

		t = findLCA(root, 2, 4);

		cout << "\nLCA(2, 4) = " << (t? t->key : -1);

		cout << endl;

		deleteTree(root);

	}

	void run_2()

	{

		root = new Node(1);

		root->left = new Node(2);

		root->right = new Node(3);

		root->left->left = new Node(4);

		root->left->right = new Node(5);

		root->right->left = new Node(6);

		root->right->right = new Node(7);

		Node *lca =  findLCA(root, 4, 5);

		if (lca != NULL)

			cout << "LCA(4, 5) = " << lca->key;

		else

			cout << "Keys are not present ";

		lca =  findLCA(root, 4, 10);

		if (lca != NULL)

			cout << "\nLCA(4, 10) = " << lca->key;

		else

			cout << "\nKeys are not present ";

		cout<<endl;

		deleteTree(root);

	}

	~LCANormalTree()

	{

		if (root) deleteTree(root);

	}

	void deleteTree(Node *&r)

	{//注意不能是*r。要*&r，由于须要改动r为NULL，防止多次释放

		if (r)

		{

			deleteTree(r->left);

			deleteTree(r->right);

			delete r; r = NULL;

		}

	}

};