Symmetric Tree

Условие

Дано бинарное дерево, необходимо определить, является ли оно зеркально симметричным относительно своего центра.

Примеры

Input: root = [1, 2, 2, 3, 4, 4, 3]

Output: true

Input: root = [1, 2, 2, null, 3, null, 3]

Output: false

Решение

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
fun isSymmetric(root: TreeNode?): Boolean {
		// Вложенная функция для проверки зеркальности двух поддеревьев
		fun isMirror(left: TreeNode?, right: TreeNode?): Boolean {
		    // Оба поддерева пустые — симметрично
		    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)
		}
		    
		// Если корня нет, дерево считается симметричным
		return root == null || isMirror(root.left, root.right)
}

Временная сложность

O(n), где n — количество узлов в дереве. Мы проходим по каждому узлу один раз.

Пространственная сложность

O(h), где h — высота дерева, что связано с глубиной рекурсии.