Symmetric Tree - LeetCode

Problem

1. input: 트리의 루트 노드 root
2. output: 트리가 좌우 대칭인지 Boolean 리턴
   • The number of nodes in the tree is in the range [1, 1000].
   • 100 <= Node.val <= 100

Idea

이전 문제(100. Same Tree)의 1에서 사용했던 순회를 사용하여 루트노드의 왼쪽을 전위순회, 오른쪽을 후위순회하여 비교하면 대칭여부를 확인할 수 있다 → Sol1

2에서 사용한 재귀를 통한 각 노드 비교를 좌우를 바꾸어 사용하면 좌우 대칭여부를 확인할 수 있다 → Sol2

Solution

1. 전위, 후위 탐색

   루트의 왼쪽 자식은 전위 탐색

   루트의 오른쪽 자식은 후위 순회

   class Solution {
       fun isSymmetric(root: TreeNode?): Boolean {
           return preOrder(root!!.left) == postOrder(root!!.right)
       }
       fun preOrder(p: TreeNode?, level: Int = 1): String {
           if (p == null) return ""
           return preOrder(p.left, level+1) + level.toString() + ":" + p.`val`.toString() + "," + preOrder(p.right, level+1)
       }
       fun postOrder(p: TreeNode?, level: Int = 1): String {
           if (p == null) return ""
           return postOrder(p.right, level+1) + level.toString() + ":" + p.`val`.toString() + "," + postOrder(p.left, level+1)
       }
   }
   

   시간 복잡도: 전위 순회 + 후위 순회 = n

   

2. 재귀

   노드의 좌우를 바꾸어 재귀 탐색

   class Solution {
       fun isSymmetric(root: TreeNode?): Boolean {
           var p = root!!.left
           var q = root!!.right
           if (p == null && q == null) return true
           if (p == null || q == null || p.`val` != q.`val`) return false
           return isSameTree(p.left, q.right) && isSameTree(p.right, q.left)
       }
       fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
           if (p == null && q == null) return true
           if (p == null || q == null || p.`val` != q.`val`) return false
           return isSameTree(p.left, q.right) && isSameTree(p.right, q.left)
       }
   }
   

   시간 복잡도: 트리 탐색 = n

   

Point