본문 바로가기

알고리즘풀이

Leetcode: Symmetric Tree: 트리 대칭성 검증

문제설명

  • 인자로 주어진 트리 노드의 대칭성을 검증하라

문제풀이

  • 루트부터 왼쪽과 오른쪽 노드의 값이 같은지 검사한다.
  • 자식 노드는 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
    }

}