Leetcode [Binary Tree] 101. Symmetric Tree [Easy]

in CodingTest

101. Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

https://assets.leetcode.com/uploads/2021/02/19/symtree1.jpg

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

Example 2:

https://assets.leetcode.com/uploads/2021/02/19/symtree2.jpg

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

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 100 <= Node.val <= 100
  • 문제 설명
  • Binary Tree의 root 노드가 주어집니다.
  • root 노드를 기준으로 left와 right가 mirrored 되는지 확인하는 문제입니다.
  • 문제 풀이
  • rootNode의 왼쪽 tree는 left → right 순으로 정렬되도록 탐색하여 leftNodes에 저장합니다.
  • [2,3,-101,-101,4,-101,-101]
  • rootNode의 오른쪽 tree는 right → left 순으로 정렬되도록 탐색하여 rightNodes에 저장합니다.
  • [2,3,-101,-101,4,-101,-101]
  • 각각의 노드를 탐색할 때, 더이상 자식노드가 없는 노드는 -101의 값을 저장하도록 하였습니다.
  • Example2와 같이 탐색 시 저장된 node의 배열이 같게 나오는것을 방지하기 위해 문제에서 제시된 100 <= Node.val <= 100 의 조건을 위반하는 일종의 트릭값을 넣었습니다.
  • 각각의 정렬된 node가 같은지 비교하여 결과값을 리턴해줍니다

swift 코드는 아래와 같습니다.

/**
 * 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 {
        var leftNodes: [Int] = []
        var rightNodes: [Int] = []
        
        func orderLtoR(_ node: TreeNode?, _ values: inout [Int]) {
            if node != nil {
                values.append(node!.val)
                orderLtoR(node!.left, &values)
                orderLtoR(node!.right, &values)
            } else {
                values.append(-101)
            }
        }
        
        func orderRtoL(_ node: TreeNode?, _ values: inout [Int]) {
            if node != nil {
                values.append(node!.val)
                orderRtoL(node!.right, &values)
                orderRtoL(node!.left, &values)
            } else {
                values.append(-101)
            }
        }
        
        orderLtoR(root?.left, &leftNodes)
        orderRtoL(root?.right, &rightNodes)
        
        return leftNodes == rightNodes
    }
}