Leaf-Similar Trees

1package pkg5leetcode.official75;2 3/*4 * Leaf-Similar Trees | LC 8725 * APPROACH: DFS collect leaf sequences; compare lists.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class official75_LC872LeafSimilarTrees {11    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */12 13    static class TreeNode {14        int val;15        TreeNode left, right;16        TreeNode(int val) { this.val = val; }17    }18 19    static void leaves(TreeNode node, List<Integer> out) {20        if (node == null) return;21        if (node.left == null && node.right == null) { out.add(node.val); return; }22        leaves(node.left, out);23        leaves(node.right, out);24    }25 26    static boolean leafSimilar(TreeNode root1, TreeNode root2) {27        List<Integer> a = new ArrayList<>(), b = new ArrayList<>();28        leaves(root1, a);29        leaves(root2, b);30        return a.equals(b);31    }32 33    public static void main(String[] args) {34        TreeNode a = new TreeNode(3); a.left = new TreeNode(5); a.right = new TreeNode(1);35        a.left.left = new TreeNode(6); a.left.right = new TreeNode(2);36        TreeNode b = new TreeNode(3); b.left = new TreeNode(5); b.right = new TreeNode(1);37        b.left.left = new TreeNode(6); b.left.right = new TreeNode(2);38        check(leafSimilar(a, b), "case1");39        TreeNode c = new TreeNode(1); c.left = new TreeNode(2);40        TreeNode d = new TreeNode(1); d.right = new TreeNode(3);41        check(!leafSimilar(c, d), "case2");42        System.out.println("all tests passed");43    }44 45    static void check(boolean cond, String name) {46        if (!cond) throw new AssertionError("FAILED: " + name);47        System.out.println("  PASS " + name);48    }49}