BinaryTree_LeetCode_Symmetric Tree [swift]
https://leetcode.com/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-100-liked
오답인 문제 접근
- root의 left를 root로 시작하는 left를 먼저 확인하는 중위 탐색을 수행. val을 array에 append
- root의 right를 root로 시작하는 right를 먼저 확인하는 중위 탐색을 수행. val을 array에 append
- 두 array를 비교하여 정답 반환
/**
* Definition for a binary tree node.
* 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
* }
* }
*/
class Solution {
func isSymmetric(_ root: TreeNode?) -> Bool {
guard let root = root else { return true }
var left = [Int?]()
var right = [Int?]()
func leftFirstTraversal(next node: TreeNode) {
if let lhs = node.left {
leftFirstTraversal(next: lhs)
} else {
left.append(nil)
}
left.append(node.val)
if let rhs = node.right {
leftFirstTraversal(next: rhs)
} else {
left.append(nil)
}
}
func rightFirstTraversal(next node: TreeNode) {
if let rhs = node.right {
rightFirstTraversal(next: rhs)
} else {
right.append(nil)
}
right.append(node.val)
if let lhs = node.left {
rightFirstTraversal(next: lhs)
} else {
right.append(nil)
}
}
if let lhs = root.left {
leftFirstTraversal(next: lhs)
}
if let rhs = root.right {
rightFirstTraversal(next: rhs)
}
print(right , left)
return right == left
}
}
오답 사유
195 / 199 testcases passed
input: [1,2,2,2,null,2]
print stdout: [nil, Optional(2), nil, Optional(2), nil] [nil, Optional(2), nil, Optional(2), nil]
트리가 불완전하게 들어온 경우를 비교해낼 수 없다.
그리고 꼭 전체 트리를 전부 탐색해야만 한다.
새로운 문제 접근
- root의 left, right에서 탐색을 수행한다.
- 양쪽의 val, left, right를 비교한다.
정답 코드
/**
* Definition for a binary tree node.
* 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
* }
* }
*/
class Solution {
func isSymmetric(_ root: TreeNode?) -> Bool {
guard let root = root else { return true }
var leftQueue = [TreeNode]()
var rightQueue = [TreeNode]()
var sol = true
if let lhs = root.left {
leftQueue.append(lhs)
}
if let rhs = root.right {
rightQueue.append(rhs)
}
while !leftQueue.isEmpty || !rightQueue.isEmpty {
if leftQueue.isEmpty || rightQueue.isEmpty {
sol = false
break
}
let left = leftQueue.removeFirst()
let right = rightQueue.removeFirst()
if left.val != right.val
|| left.left?.val != right.right?.val
|| left.right?.val != right.left?.val {
sol = false
break
}
if let Lleft = left.left {
leftQueue.append(Lleft)
}
if let Lright = left.right {
leftQueue.append(Lright)
}
if let Rright = right.right {
rightQueue.append(Rright)
}
if let Rleft = right.left {
rightQueue.append(Rleft)
}
}
return sol
}
}코드 해설
if let lhs = root.left {
...
if let rhs = ...
부분은 처음엔 guard 문으로 rhs, lhs를 한 번에 선언했다.
guard let rhs = root.right, let lhs = root.left else { return false }
이 경우, input이 [0, 1] 인 경우와 [0]인 경우 두 경우에 대한 대처를 동시에 할 수 없었다.
그래서 개별적으로 optionalBinding한 이후 queue에 넣어주었다.
대신, while문 내부에서 검사하도록 하였다.
while문은 두 queue모두 비어야 순회를 마친다.
둘 중 한 queue만 비어있을 경우, 종료하고 false를 반환한다.
두 queue의 첫번째 원소를 꺼내어 val, left.val, right.val을 서로 비교한다.
이 때 거울상이어야 하므로, 좌우를 교차하여 비교한다.
그리고 left, right의 자식 노드를 queue에 추가하는데, 이 때에도 left, right가 교차하도록 추가한다.