본문 바로가기
코딩 공부

[Binary Tree / 이진트리] Solve Tree Problems Recursively / Maximum Depth of Binary Tree

by 카우보이연구소 2022. 1. 20.

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

 

문제: 오늘은 문제가 아니라, Recursion lesson
등급: ---

<코드>

두가지 방법, 솔루션이 주어진다.

 

첫번째는, "top-down" solution.

이렇게 definition이 적혀있다: 

"Top-down" means that in each recursive call, we will visit the node first to come up with some values, and pass these values to its children when calling the function recursively.

매번 node를 위에서 아래로 내려갈때마다, value가 나오게 만들고, 그 value가 밑으로 node의 children에게 가도록? 적어보니 이상하다. 어쨌든 요약하자면 꾸준히 재귀 호출을 통해 value가 밑으로 가게 함 된다.

 

leetcode에서 보여주는 top_down(root,params) function에 대한 psuedocode는 이렇다:

1. return specific value for null node
2. update the answer if needed                      // answer <-- params
3. left_ans = top_down(root.left, left_params)      // left_params <-- root.val, params
4. right_ans = top_down(root.right, right_params)   // right_params <-- root.val, params
5. return the answer if needed                      // answer <-- left_ans, right_ans

1. node가 null이라면, specific value (-1, 0 이나 none이나 뭐 [], () 등)을 반환

2. 마지막으로 return 할 답을 update (필요하다면) [계속 update하는 것이 중요할 듯]

3. 재귀호출을 해준다. (왼쪽 답)

4. 3번과 마찬가지

5. return 답 (특정한 경우 if?)

 

이정도로 이해했다.

 

Leetcode에는 C++와 JAVA로만 적혀있는데, 한 번 나의 solution을 적어보자:

maximum_depth(root, depth)

ans = 0
def maximum_depth(self, root, depth):
	if not root:
    	return 0
    if not root.left and not root.right:
    	ans = max(ans, depth)
    
    maximum_depth(root.left, depth + 1)
    maximum_depth(root.right, depth + 1)
    
    #이거 아닌 듯 하다

이게 아닌 것 같긴 한데, 우선 Java랑 C++로 적혀있는 것 대충 이렇게 생겼다.

 

2번째 방법, "Bottom-Up" Solution

 

위에서 아래로 내려가는 대신, 아래에서 위로 올라온다. 이에 대한 유튜브 비디오도 하나 봤는데,  그 사람이 말하길, "앞에서부터 1! 2! 3!" ... 군대식 고개 돌려 번호 말하는 점호시간이 생각났다. 이해가 쉬웠다.

 

밑에는 leetcode에서 말하는 solution의 논리

1. return specific value for null node
2. left_ans = bottom_up(root.left)      // call function recursively for left child
3. right_ans = bottom_up(root.right)    // call function recursively for right child
4. return answers                       // answer <-- left_ans, right_ans, root.val

그리고 내가 적은 코드 (for maximum depth)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):
        if root is None:
            return 0
        
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        
        return max(left, right) + 1

밑에 root가 없으면 0이 되며, +1 +1 재귀 호출을 통해 결국에는 depth가 구해진다.

<오류, 힘들었던 점>

처음에는 위 코드의 아이디어를 몰라서, 한참 헤맸던 기억이 있다.

 

<총평>

 

Happy coding!

 

Account Login - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

댓글