(LeetCode) 101. Symmetric Tree

Symmetric Tree

• Explore : Interview > Top Interveiw Questions > Easy Collection
• 분류 : Trees
• 난이도 : Easy

Problem

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

Example 1

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

Example 2

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

Solution - Recursive

Exapnder

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isSymmetric(root: TreeNode?): Boolean {
        if (root == null) {
            return true
        }
        return recursive(root.left, root.right)
    }
    
    fun recursive(left: TreeNode?, right: TreeNode?): Boolean {
        if (left == null && right == null) {
            return true
        }
        else if (left == null || right == null) {
            return false
        }
        else if (left.`val` != right.`val`) {
            return false
        }
        return recursive(left.left, right.right) && recursive(left.right, right.left)
    }
}

Solution - Iterative

Exapnder

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isSymmetric(root: TreeNode?): Boolean {
        if (root == null) {
            return true
        }
        var queue: Queue<Pair<TreeNode, TreeNode>> = LinkedList()
        queue.add(Pair(root, root))
        
        while (queue.isNotEmpty()) {
            var node = queue.poll()
            var left = node.first
            var right = node.second
            if (left != null || right != null) {
                if (left != null && right != null && left.`val` == right.`val`) {
                    queue.add(Pair(left.left, right.right))
                    queue.add(Pair(left.right, right.left))
                } else {
                    return false
                }
            }
        }
        return true
    }

}

Point of Thinking

• 문제에서 재귀와 반복을 다 구현해보는 게 추천되어서 두 가지 방법으로 풀이해보았다.
• 재귀든 반복이든 대칭트리를 증명하는 규칙은 아래와 같다.
  • 1. left / right가 둘 다 null이면 leaf node가 없으므로 true
  • 2. left와 right 둘 중 하나라도 null이면 false
  • 3. left와 right의 값이 다르면 false
  • 4. 그 외 조건은 다시 한 번 재귀 혹은 반복
• 대칭트리이므로 파라미터가 조금 독특하게 느껴질 수도 있다. 휴먼에러에 주의하자.