236.Lowest Common Ancestor of a Binary Tree

1-Recursion

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/65225/

Same solution in several languages. It’s recursive and expands the meaning of the function. If the current (sub)tree contains both p and q, then the function result is their LCA. If only one of them is in that subtree, then the result is that one of them. If neither are in that subtree, the result is null/None/nil.

/**
 * 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) {
        if(root == null || root == p || root == q){
            return root;
        }
        else{
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            // if both in right;
            if(left == null){
                return right;
            }
            // if both in left
            else if(right == null){
                return left;
            }
            // if one is in left, another is in right
            else{
                return root;
            }
        }
    }
}