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

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

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

#include 
     
      #include 
      
       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
       
         &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
        
          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; } } };