Lowest Common Ancestor of A Binary Tree

Description

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

Code

This is a cliche question, we can use recursion to solve it, each time we will check the left child and right child, if each ancestor is not null, the current node must be the LCA, else return the non-null node.

/**
 * 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) return null;
        if (root == p || root == q) return root;
        
        TreeNode left_ancestor = lowestCommonAncestor(root.left, p, q);
        TreeNode right_ancestor = lowestCommonAncestor(root.right, p, q);
        if (right_ancestor != null && left_ancestor != null) return root;
        
        return left_ancestor != null ? left_ancestor:right_ancestor;
    }
}