Lowest Common Ancestor of a Binary Tree

1package pkg5leetcode.official75;2 3/*4 * Lowest Common Ancestor of a Binary Tree | LC 2365 * APPROACH: Post-order return node if p/q found in subtree.6 * COMPLEXITY: Time O(n), Space O(h)7 */8public class official75_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    }16 17    static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {18        if (root == null || root == p || root == q) return root;19        TreeNode left = lowestCommonAncestor(root.left, p, q);20        TreeNode right = lowestCommonAncestor(root.right, p, q);21        if (left != null && right != null) return root;22        return left != null ? left : right;23    }24 25    public static void main(String[] args) {26        TreeNode root = new TreeNode(3);27        TreeNode p = new TreeNode(5), q = new TreeNode(1);28        root.left = p; root.right = q;29        p.left = new TreeNode(6); p.right = new TreeNode(2);30        q.left = new TreeNode(0); q.right = new TreeNode(8);31        p.right.left = new TreeNode(7); p.right.right = new TreeNode(4);32        check(lowestCommonAncestor(root, p, q) == root, "case1");33        TreeNode p2 = p.right, q2 = p.right.right;34        check(lowestCommonAncestor(root, p2, q2) == p2, "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}