Leetcode 993. Cousins in Binary Tree

월요일의 시작이다! 

요즘 주말도 좋지만 월요일도 너무 좋은거 있지...

뭔가 나는 뭐든 할 수 있을 것 같은 자신감이 뿜뿜 넘치고 

이번주에는 어떤 연구를 하고 무슨 논문을 읽을지 고르는 과정이 기대(?) 가 되기도 한다.

물론 한 수요일쯤 되면 주말 언제오나 기다리게 되지만...

암튼 월요일의 시작을 연구실에서 데이터 확인하고, 바로 리트코드로 !! 했다 신난당

 

오늘은 Binary tree에서 사촌 찾기이다.

뭔가 사촌이라 하니까 웃기긴 한데 ㅋㅋㅋ

여튼 사촌이다.

부모가 다르고, depth가 같은 것을 "cousins"라고 한다!

 

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        answer = []
        def DFS(node, depth, parent):
            if not node:
                return
            if node.val == x or node.val == y:
                answer.append((parent, depth))
                
            DFS(node.left, depth + 1, node.val)
            DFS(node.right, depth + 1, node.val)
            
            return
        
        DFS(root, 0, None)
        
        return (answer[0][0] != answer[1][0]) and (answer[0][1] == answer[1][1])

 

오늘도 DFS인데, 코드가 좀 조잡스러운 느낌은 뭐람..?

여태 DFS 중 어떤 것을 리턴하는 형식은 많이 짜보지 않은 것 같은데, 역시나 어디서 무엇을 리턴해야하는지 생각하면서 짜다가 버벅거리고 실패를 많이 했다 ...

 

그래서 결국 생각해 낸 방식은,,

DFS를 내장 함수로 넣을거니까 쉽게 answer에 넣자는 것!

 

처음에는 조잡하고 DFS를 x에 한 번, y에 한 번 돌리는 코드를 짰는데...

이렇게 되면 한 번 돌거 두번 돌게 되는 낭비가 발생해서 x or y를 찾는 문제로 하였다.

어차피 찾는 값은 한 번만 순회하면 다 찾을 수 있으니까!!!!!!!!!!

그럼 한 번 다 돌면 answer에 [(x_parent, x_depth), (y_parent, y_depth)]가 저장이 된다.

(위는 x가 먼저 찾아졌다는 가정 하에 x를 먼저 배치하였다.)

 

그럼 이제 쉬워진다.

x_parent != y_parent and x_depth == y_depth 하면 끝!

 

 

오늘도 다섯번의 실패를 거쳐 Success를 얻어냈다! 왕멋져

오늘도 아침부터 5번의 실패를 쌓았다 야호~

 

오늘의 리트코드 끝!

---

점점 실패 횟수가 늘어나는 것을 보니 나의 성공이 멀리 있지 않은가보다. 한 5년 후...?ㅋㅋ

 

예전에는 나의 실패가 한없이 부끄럽고, 이런것도 못하나 싶기도 하고,

남들은 잘만 성공하는데 왜 나는 실패할까 생각이 들었다.

그리고 나도 남들한테 성공한 것만 보여주고 싶었고, 그저 잘 하고 싶었다.

 

그런데 몇 주 전 교수님과의 개인 미팅에서 교수님이 처음부터 잘 하는 건 말도 안되는 것이다,

실패를 지금 많이 겪어봐야 나중에 실패를 해도 일어날 수 있다는 말씀을 해주셨다.

지금 성공만을 맛본다면, 나는 후에 실패를 하였을 때 일어나지도 못하고 주저앉게 될 것이다.

그러니까 지금은 성공만을 향해서 달려간다기 보다는 실패를 통해 많은 경험을 쌓을 때 인 것이다.

 

오늘도 많은 실패를 통해 더욱 성장하는 내가 되었으면 좋겠다.