236. Lowest Common Ancestor of a Binary Tree Given.md

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left == null ? right : left;
    }
}

note

• Recursion. Recursively traversing left and right subtree. What lowestCommonAncestor() function does is: 1). If the root is p or q itself, return the root directly. 2). If the returned left and right nodes of the root node both are not null, then the root is LCA. 3). If one of left and right nodes is not null, return the node that is not null.