Is the Tree a Mirror of Itself

easy tree dfs recursion

Problem

Given the root of a binary tree, decide whether the tree is a mirror of itself — left subtree is the mirror of the right subtree. Two subtrees mirror each other if their roots match and the left of one mirrors the right of the other (and vice versa).

Walk a pair of pointers (L, R) outward from the root. At each step compare values, then recurse on (L.left, R.right) and (L.right, R.left).

Inputlevel-order: [1, 2, 2, 3, 4, 4, 3]

Outputtrue

Outermost pair (2, 2) matches; next pairs (3, 3) and (4, 4) match too.

level-order ('_' for null)

def is_symmetric(root):
    def mirror(L, R):
        if L is None and R is None: return True
        if L is None or R is None: return False
        if L.val != R.val: return False
        return mirror(L.left, R.right) and mirror(L.right, R.left)
    return root is None or mirror(root.left, root.right)

function isSymmetric(root) {
  function mirror(L, R) {
    if (!L && !R) return true;
    if (!L || !R) return false;
    if (L.val !== R.val) return false;
    return mirror(L.left, R.right) && mirror(L.right, R.left);
  }
  return !root || mirror(root.left, root.right);
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || mirror(root.left, root.right);
    }
    private boolean mirror(TreeNode L, TreeNode R) {
        if (L == null && R == null) return true;
        if (L == null || R == null) return false;
        if (L.val != R.val) return false;
        return mirror(L.left, R.right) && mirror(L.right, R.left);
    }
}

bool mirror(TreeNode* L, TreeNode* R) {
    if (!L && !R) return true;
    if (!L || !R) return false;
    if (L->val != R->val) return false;
    return mirror(L->left, R->right) && mirror(L->right, R->left);
}
bool isSymmetric(TreeNode* root) {
    return !root || mirror(root->left, root->right);
}

Time: O(n) Space: O(h) recursion depth