91. Symmetric Tree

A tree is symmetric if the left subtree is a mirror reflection of the right subtree. Two trees are mirrors if their roots match and each tree's left is a mirror of the other's right.

Approach

1. Compare left and right subtrees recursively.
2. Two nodes are mirrors if they have the same value, and left.left mirrors right.right, and left.right mirrors right.left.

Complexity

• Time: O(n)
• Space: O(h)

class Solution {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        return left.val == right.val
            && isMirror(left.left, right.right)
            && isMirror(left.right, right.left);
    }
}