Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

&nbsp;
Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.


Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.


Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [2, 105].
	-109 &lt;= Node.val &lt;= 109
	All Node.val are unique.
	p != q
	p and q will exist in the tree.


class Solution:
    # @param {TreeNode} root
    # @param {TreeNode} p
    # @param {TreeNode} q
    # @return {TreeNode}
    def lowestCommonAncestor(self, root, p, q):
        # escape condition
        if (not root) or (root == p) or (root == q):
            return root
        # search left and right subtree
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            # both found, root is the LCA
            return root
        return left or right
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path_to_p= new ArrayList<>();
        List<TreeNode> path_to_q= new ArrayList<>();
        getPath(root,p,path_to_p);
        getPath(root,q,path_to_q);
        int n=path_to_q.size()>path_to_p.size()?path_to_p.size():path_to_q.size();
        TreeNode anscesstor=root;
        for(int i=0;i<n;i++){
            if(path_to_q.get(i)==path_to_p.get(i)) anscesstor=path_to_p.get(i);
        }
        return anscesstor;
        
        
    }
    
    boolean getPath(TreeNode root, TreeNode target,List<TreeNode> list){
        if(root==null) return false;
        list.add(root);
        if(root==target) return true;
        if(getPath(root.left,target,list) || getPath(root.right,target,list)){
            return true;
        }
        list.remove(list.size()-1);
        return false;
    }
}
class Solution
{
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if(!root)
        {
            return NULL;
        }
        if(root==p or root == q)
        {
            return root;
        }
        TreeNode *left=lowestCommonAncestor(root->left,p,q);
        TreeNode *right=lowestCommonAncestor(root->right,p,q);
        if(left and right) return root;
        if(left) return left;
        else return right;

    }
};
var lowestCommonAncestor = function(root, p, q) {
    if(!root || root.val == p.val || root.val == q.val) return root;

    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);

    return (left && right) ? root : left || right;
};
Lowest Common Ancestor of a Binary Tree