// MARK: - 101. Symmetric Tree

//        1
//      /   \
//     2     2
//    / \   / \
//   3   4 4   3

// сравнить надо 2 и 2 (как значения)
// и запустить рекурсию на сравнение 3(left) и 3(right) и 4(right) и 4(left)

func isSymmetric(_ root: TreeNode?) -> Bool {

    func dfs(leftSub: TreeNode?, rightSub: TreeNode?) -> Bool {
        // базовым случаем будет то, что и левый и правый nil - они симметричны
        if leftSub == nil && rightSub == nil {
            return true
        }

        // Один из равен nil - не симметричны
        if leftSub == nil || rightSub == nil {
            return false
        }


        // Проверяем значения. Но не только они должны быть равны. Нужно еще сравнить поддеревья внешние и внутренние
        // Возвращаем результат всех сравнений. Если хотя бы что-то вернуло false -> false
        return (leftSub?.val == rightSub?.val
                    &&  dfs(leftSub: leftSub?.left, rightSub: rightSub?.right)
                        &&  dfs(leftSub: leftSub?.right, rightSub: rightSub?.left))
    }

    return dfs(leftSub: root?.left, rightSub: root?.right)
}