[Top Interview Questions] 101. Symmetric Tree

요즘_코딩.png

정답)

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        # Recursive Function
        def helper(leftRoot, rightRoot):
            # Base Case
            if not leftRoot and not rightRoot:
                return True
                
            # 두 노드가 둘 다 존재해 비교가 가능할 때
            if leftRoot and rightRoot:
                # left의 left와 right의 right을 비교한 결과를 저장
                res1 = helper(leftRoot.left, rightRoot.right)
                
                # left의 right과 right의 left를 비교한 결과를 저장
                res2 = helper(leftRoot.right, rightRoot.left)
                
                # children 비교 결과 2개와 parent 비교 결과 1개를 종합하여 리턴
                return res1 and res2 and (leftRoot.val == rightRoot.val)
        
            # 두 노드 중 하나가 존재하지 않아 무조건 symmetric이 아닐 때
            else:
                return False

        # recursive func 실행
        return helper(root.left, root.right)

문제)

문제출처

 

binary tree의 루트가 주어졌을 때, 트리의 중심을 기점으로 대칭인지 확인하시오.

 

예시 1)

 

root = [1, 2, 2, 3, 4, 4, 3]

root = [1, 2, 2, 3, 4, 4, 3]

output = True

 

예시 2)

root = [1, 2, 2, Null, 3, Null, 3]

output = False

 

제한)

트리의 노드의 개수는 1~1000개 입니다. 

-100 <= 노드의 val <= 100

풀이)

기본원리)

트리의 가장 아래에서부터 비교하면서 올라가는 방식

 

가장 아래의 parent 노드와 그 children 노드 2개 총 3개의 노드가 있습니다.

반대편에도 똑같이 3개의 노드가 있을겁니다.

 

3쌍의 노드를 비교

이렇게 3 쌍의 노드를 위치에 맞게 비교 후 얻어온 bool 값을 and 기호로 비교해 최종적 bool 값을 구합니다.

이런 식으로 recursive하게 트리의 꼭대기까지 갑니다.

 

bool1 and bool2 and bool3

그렇게 얻은 최종 bool 값을 리턴하면 됩니다.

Recursive 함수 만들기)

저번 문제와 비슷하게 이번에도 recursive하게 문제를 다가가 볼겁니다. 

제가 iterative를 생각할 여유도 없긴하지만 (헤헤...) recursive 함수를 더럽게 못 만들기 때문에 연습겸 해봅시다.

 

일단 recursive function의 루프를 끝내줄 base case가 필요합니다.

 

제한에서 노드의 갯수가 1 이상이라고 했기 때문에 root는 무조건 존재합니다.

그러므로 root가 존재하는지 보다는 root의 left/right 노드가 존재하는지 확인하는 것이 좋을 것 같습니다.

 

그리고 만약 root의 left/right 노드가 둘 다 Null이라면 대칭이죠?

 

이럴 경우 True를 리턴

 

그러므로 위 조건에서 True를 리턴해 루프를 끝내줍시다.

 

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def helper(leftRoot, rightRoot):
            if not leftRoot and not rightRoot:
                return True

Recursive Calls 1)

하지만 만약 left/right 노드들이 둘 다 존재한다면 어떻게 해야될까요?

 

그럴 경우엔 left/right 노드들의 val값을 비교하는 것도 중요하지만

그 아래 children 노드들의 val값을 비교하는 것도 중요합니다.

 

노드들을 비교하는 순서

그리고 recursive calls를 디자인할 때는 단순하게 생각해야된다고 했죠?

helper() 함수는 주어진 노드 그 밑으로 저희가 원하는 결과를 리턴하도록 디자인할 예정입니다.

 

그럼 그 디자인에 맞게 일단은 큰 그림으로 적어줍니다.

 

left의 left와 right의 right을 비교하는 코드 한 줄

left의 right과 right의 left를 비교하는 코드 한 줄

 

위 두 줄이 left/right 노드들 밑에 결과를 전부 계산해서 원하는 bool 값을 리턴했다고 가정합시다.

그럼 left/right 노드들 밑의 노드들은 전부 비교가 끝났으니 남은 것은 left/right 노드들 뿐입니다.

 

그래서 아까 찾은 아래의 노드들이 대칭한지 저장한 bool 값 res1, res2들과 현재 left/right 노드들을 비교해서 얻는 bool 값을 최종적으로 비교하여 전체 트리가 대칭한지 리턴해줍시다. 

 

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def helper(leftRoot, rightRoot):
            if not leftRoot and not rightRoot:
                return True
            
            if leftRoot and rightRoot:
                res1 = helper(leftRoot.left, rightRoot.right)
                res2 = helper(leftRoot.right, rightRoot.left)
                return res1 and res2 and (leftRoot.val == rightRoot.val)

Recursive Calls 2)

지금까지 적은 조건들은 left/right 노드들 전부 존재하는지 혹은 안존재하는지 입니다. 

 

만약 둘 중 하나라도 존재하지 않는다면 어떻게 해야될까요?

바로 False를 리턴해주시면 됩니다.

 

왜냐하면 둘 중 하나라도 없다는 것은 이미 비대칭이라는 것이기 때문입니다.

 

이제 recursive 함수가 완성 되었으니 이 함수를 실행하면 끝나겠습니다.

 

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def helper(leftRoot, rightRoot):
            if not leftRoot and not rightRoot:
                return True
            
            if leftRoot and rightRoot:
                res1 = helper(leftRoot.left, rightRoot.right)
                res2 = helper(leftRoot.right, rightRoot.left)
                return res1 and res2 and (leftRoot.val == rightRoot.val)
        
            else:
                return False

        return helper(root.left, root.right)

디버깅)

root = [1, 2, 2]

 

root = [1, 2, 2]

 

helper(2, 2) 

res1 = helper(Null, Null)

 

helper(Null, Null)

return True

res 1 = True

 

res 2 = helper(Null, Null)

 

helper(Null, Null)

return True

res 2 = True

 

return res1 and res2 and (2.val == 2.val)

return True and True and True

 

return True

 

 

이 것보다 한 칸만 더 많아져도 디버깅의 길이가 너무 길어지겠더라구요. 그래서 예시가 조금 짧은 걸 골랐습니다.

이번 문제는 저번 문제보다는 조금 쉽게 설명한 것 같은데 도움이 되셨나요? (그래도 Recursion은 어렵다 ㅎ...)

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)