236. Lowest Common Ancestor of a Binary Tree

Medium

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).”

Given the following binary tree:  root = [3,5,1,6,2,0,8,null,null,7,4]

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.

Idea:
Recursively search for p an q from bottom up
1. If the root match with p or q, return root. it means p or q is present in binary tree.
2. If the root doesn't match with any of the keys, look for the keys in left substring and right substring.
    If one key is present in left substring, the other key is present in right substring. this root is LCA, return the root.
    If both keys are present in left subtree,  and left subtree has LCA, return LCA.
    If both keys are present in right subtree, and right subtree has LCA, return LCA.

class Solution {
    public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(root == p || root == q) return root;
        TreeNode left = LCA(root.left,p,q);
        TreeNode right = LCA(root.right,p,q);
        if(right!= null && left != null){
            return root;
        }else if(left!= null){
            return left;
        }else if(right != null){
            return right;
        }
        return null;
    }
}