# Java solution by finding the path for each node

• Find the path for each node.
Compare each path to find the LCA

``````public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
if(root==null) return null;
if(p==null || q==null)  return null;
ArrayList<TreeNode> p_path = new ArrayList<TreeNode>();
ArrayList<TreeNode> q_path = new ArrayList<TreeNode>();
findPath(root, p, p_path);
findPath(root, q, q_path);
int min_len = Math.min(p_path.size(), q_path.size());
int LCA = 0;
for(int i=0; i<min_len; i++){
if(p_path.get(i)==q_path.get(i))
LCA = i;
}return p_path.get(LCA);

}
public static boolean findPath(TreeNode root, TreeNode n1, List<TreeNode> path){
if(root == null)
return false;
if(root == n1)
return true;
if(findPath (root.left, n1, path) || findPath(root.right, n1, path))
return true;
path.remove(path.size() - 1);
return false;
}``````

• I have the same idea with you

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

``````    // use the depth first algorithm to get the path of p and q
vector<TreeNode*> p_path;
getPath(root, p, p_path);
vector<TreeNode*> q_path;
getPath(root, q, q_path);

vector<TreeNode*> common_path;
TreeNode *low_comm = 0;
int min_length = min(p_path.size(), q_path.size());

for (int i = 0; i < min_length; i++){
if (p_path[i] == q_path[i]){
low_comm = p_path[i];
}

else break;
}

return low_comm;

}

// get the path of one node
bool getPath(TreeNode* node, TreeNode *p, vector<TreeNode*>& node_path){

if (node == NULL) return false;

node_path.push_back(node);
if (node == p) return true;

if (getPath(node->left, p, node_path)|| getPath(node->right, p, node_path)) return true;

node_path.pop_back();

return false;

}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.