Subtree of Another Tree

1package pkg5leetcode.blind75;2 3/*4 * Subtree of Another Tree | LC 5725 * APPROACH: DFS root; at each node check same-tree match.6 * COMPLEXITY: Time O(mn), Space O(h)7 */8public class blind75_LC572SubtreeOfAnotherTree {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 boolean isSubtree(TreeNode root, TreeNode subRoot) {18        if (root == null) return false;19        if (same(root, subRoot)) return true;20        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);21    }22 23    static boolean same(TreeNode a, TreeNode b) {24        if (a == null || b == null) return a == b;25        return a.val == b.val && same(a.left, b.left) && same(a.right, b.right);26    }27 28    public static void main(String[] args) {29        TreeNode root = new TreeNode(3);30        root.left = new TreeNode(4);31        root.right = new TreeNode(5);32        root.left.left = new TreeNode(1);33        root.left.right = new TreeNode(2);34        TreeNode sub = new TreeNode(4);35        sub.left = new TreeNode(1);36        sub.right = new TreeNode(2);37        check(isSubtree(root, sub), "case1");38        TreeNode sub2 = new TreeNode(4);39        sub2.left = new TreeNode(1);40        check(!isSubtree(root, sub2), "case2");41        System.out.println("all tests passed");42    }43 44    static void check(boolean cond, String name) {45        if (!cond) throw new AssertionError("FAILED: " + name);46        System.out.println("  PASS " + name);47    }48}