法一

用两个独立的数组储存根节点到节点的路径，然后从0开始遍历。LCA是这两个数组最后匹配的元素。

// C++ program to find LCA using Arrays to Store 
// Paths of Nodes from Root
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        data = x;
        left = nullptr;
        right = nullptr;
    }
};

// Function to find path from root to given node.
bool findPath(Node* root, vector<Node*>& path, int k) {
  
    // base case
    if (root == nullptr)
        return false;

    // Store current node value in the path.
    path.push_back(root);

    // If node value is equal to k, or
    // if node exist in left subtree or
    // if node exist in right subtree return true
    if (root->data == k || 
            findPath(root->left, path, k) ||
                 findPath(root->right, path, k))
        return true;

    // else remove root from path and return false
    path.pop_back();
    return false;
}

// Returns LCA of two nodes.
Node* lca(Node* root, int n1, int n2) {
  
    // to store paths to n1 and n2 from the root
    vector<Node*> path1, path2;

    // Find paths from root to n1 and 
    // root to n2. If either
    // n1 or n2 is not present, return nullptr
    if (!findPath(root, path1, n1) || 
        !findPath(root, path2, n2))
        return nullptr;

    // Compare the paths to get the first
    // different value
    int i;
    for (i = 0; i < path1.size()
         			&& i < path2.size(); i++) {
        if (path1[i] != path2[i])
           	return path1[i-1];
    }
  	
  	// if both the datas are same, return last node
    return path1[i-1];
}

int main() {
  
  	// construct the binary tree
  	//			   1
    //           /   \
    //          2     3
    //         / \   / \
    //        4  5  6   7 
    Node* 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* ans = lca(root, 4, 5);
  	if(ans == nullptr)
      	cout<<"No common ancestor found";
	else
      	cout<< ans->data;
    return 0;
}

法二

The idea is to traverse the tree starting from the root. If any of the given keys* *(n1 and n2) matches* with the root, then the root is LCA (assuming that both keys are present). If the root *doesn’t* *match* with any of the keys, we *recur* for the *left* and *right* subtree. The node which has *one key* present in its *left* subtree and the *other key* present in the *right* subtree is the LCA, else if, both keys lie in the *left* subtree, then the *left* *subtree* has LCA, else the *LCA* lies in the *right* subtree.

// C++ program to find LCA using Single traversal
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    Node *left, *right;
    int data;
    Node(int k) {
        data = k;
        left = nullptr;
        right = nullptr;
    }
};

// Function to find LCA of two keys.
Node* lca(Node* root, int n1, int n2) {

    if (!root)
        return nullptr;

    // If either key matches with root data, return root
    if (root->data == n1 || root->data == n2)
        return root;

    // Look for datas in left and right subtrees
    Node* leftLca = lca(root->left, n1, n2);
    Node* rightLca = lca(root->right, n1, n2);

    // If both of the above calls return Non-NULL, then one
    // data is present in one subtree and the other is present
    // in the other, so this node is the LCA
    if (leftLca && rightLca)
        return root;

    // Otherwise check if left subtree or right subtree is
    // LCA
    return leftLca ? leftLca : rightLca;
}

int main() {

    // construct the binary tree
    //			   1
    //           /   \
    //          2     3
    //         / \   / \
    //        4  5  6   7 

    Node* 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* ans = lca(root, 4, 5);
    if(ans == nullptr){
        cout<<"No common ancestor found";
    }
    else{
        cout<<ans->data;
    }

    return 0;
}

上述方法依赖于两个key都必须存在树中，而实际情况不同。需要寻找是否在树中。