Symmetric Tree

1package pkg5leetcode.interview150;2 3/*4 * Symmetric Tree | LC 1015 * APPROACH: Compare left and right subtrees as mirror images.6 * COMPLEXITY: Time O(n), Space O(h)7 */8public class interview150_LC101SymmetricTree {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 isSymmetric(TreeNode root) {18        return root == null || mirror(root.left, root.right);19    }20 21    static boolean mirror(TreeNode a, TreeNode b) {22        if (a == null && b == null) return true;23        if (a == null || b == null) return false;24        return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left);25    }26 27    public static void main(String[] args) {28        TreeNode root = new TreeNode(1);29        root.left = new TreeNode(2);30        root.right = new TreeNode(2);31        root.left.left = new TreeNode(3);32        root.left.right = new TreeNode(4);33        root.right.left = new TreeNode(4);34        root.right.right = new TreeNode(3);35        check(isSymmetric(root), "case1");36        TreeNode bad = new TreeNode(1);37        bad.left = new TreeNode(2);38        bad.right = new TreeNode(2);39        bad.left.right = new TreeNode(3);40        bad.right.right = new TreeNode(3);41        check(!isSymmetric(bad), "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}