Определение зеркальной симметрии бинарного дерева

Условие

Необходимо проверить, обладает ли переданное бинарное дерево зеркальной симметрией относительно своей центральной оси.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

public boolean isSymmetric(TreeNode root) {
    // TODO
    return false;
}

Ответ

Сравнивайте левое и правое поддеревья как зеркала: значения корней равны, внешние ветви симметричны и внутренние ветви симметричны. Два пустых поддерева совпадают.

public boolean isSymmetric(TreeNode root) {
    return root == null || mirror(root.left, root.right);
}

private boolean mirror(TreeNode a, TreeNode b) {
    if (a == null || b == null) return a == b;
    return a.val == b.val
            && mirror(a.left, b.right)
            && mirror(a.right, b.left);
}

Пустое дерево считается симметричным. Время O(n), стек O(h), где h — высота дерева. Совпадения только значений недостаточно: расположение отсутствующих узлов также должно быть зеркальным. Для очень глубокого дерева используйте итеративный обход пар узлов.