문제설명
문제풀이
- 루트부터 왼쪽과 오른쪽 노드의 값이 같은지 검사한다.
- 자식 노드는 2개가 존재하므로 왼쪽과 오른쪽 노드를 검사해야 한다.
// MARK: - Answer
func isSymmetric(_ root: TreeNode?) -> Bool {
return isSymmetricHelper(root, root)
}
func isSymmetricHelper(_ node1: TreeNode?, _ node2: TreeNode?) -> Bool {
if node1 == nil && node2 == nil {
return true
}
return node1?.val == node2?.val
&& isSymmetricHelper(node1?.left, node2?.right)
&& isSymmetricHelper(node1?.right, node2?.left)
}
// MARK: - Test
var node1: TreeNode?
node1 = TreeNode.from([1,2,2,3,4,4,3])
print(isSymmetric(node1)) // true
node1 = TreeNode.from([1,2,2,nil,3,nil,3])
print(isSymmetric(node1)) // false
// MARK: - Definition
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil; }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}
extension TreeNode {
static func from(_ arr: [Int?]) -> TreeNode? {
guard let firstElement = arr[0] else {
return nil
}
let root = TreeNode(firstElement)
var queue = [TreeNode]()
queue.append(root)
var index = 1
while !queue.isEmpty && index < arr.count {
let node = queue.removeFirst()
if let leftVal = arr[index] {
let left = TreeNode(leftVal)
node.left = left
queue.append(left)
}
if index+1 < arr.count, let rightVal = arr[index+1]{
let right = TreeNode(rightVal)
node.right = right
queue.append(right)
}
index += 2
}
return root
}
}