Lowest Common Ancestor of Binary Tree

1package pkg5leetcode.interview150;2 3/*4 * Lowest Common Ancestor of Binary Tree | LC 2365 * APPROACH: Recurse; if node is p or q return it; LCA if both subtrees found.6 * COMPLEXITY: Time O(n), Space O(h)7 */8public class interview150_LC236LowestCommonAncestorOfBinaryTree {9    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */10 11    static class TreeNode {12        int val;13        TreeNode left, right;14        TreeNode(int val) { this.val = val; }15        TreeNode(int val, TreeNode l, TreeNode r) { val = val; left = l; right = r; }16    }17 18    static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {19        if (root == null || root == p || root == q) return root;20        TreeNode left = lowestCommonAncestor(root.left, p, q);21        TreeNode right = lowestCommonAncestor(root.right, p, q);22        if (left != null && right != null) return root;23        return left != null ? left : right;24    }25 26    public static void main(String[] args) {27        TreeNode p = new TreeNode(5);28        TreeNode q = new TreeNode(1);29        TreeNode root = new TreeNode(3, p, new TreeNode(4));30        p.left = q;31        p.right = new TreeNode(8);32        check(lowestCommonAncestor(root, p, q).val == 5, "case1");33        q = new TreeNode(4);34        check(lowestCommonAncestor(root, p, q).val == 5, "case2");35        System.out.println("all tests passed");36    }37 38    static void check(boolean cond, String name) {39        if (!cond) throw new AssertionError("FAILED: " + name);40        System.out.println("  PASS " + name);41    }42}