오늘의 주제도 DFS/BFS
[Maximum Depth of Binary Tree]
문제
입력과 출력
코드
# 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 maxDepth(self, root: TreeNode) -> int:
#int니까,,이거 자체를 수로..?
if not root:
return 0 #반환형이 int여서 return만 하면 안되고 0으로 반횐해줘야..했군
r_left=self.maxDepth(root.left)
r_right=self.maxDepth(root.right)
return max(r_left, r_right)+1알고리즘
먼저, 이 함수 maxDepth의 반환형은 int라는 것을 유의하고 가야한다.
지금까지의 문제와 같이 노드가 없을 때의 조건을 정의해준다. 평소에는 return 했지만, 함수의 반환형이 int이므로 return 0 으로 해주어야한다 !!
left와 right 변수에 각각의 재귀함수로 왼쪽과 오른쪽 깊이를 세어주고, 이 중 큰 값을 +1하여 반환한다.
회고
처음에 구성했던 코드.
cnt를 써주기 위해 새로 함수를 만들었었다.
그러나 이 cnt가 오류가 났고,,
인터넷 서칭을 하던 중 global로 선언해주면 지역변수도 끌어 쓸 수있는 것 같아
이런식으로 작성하였다. 그러나 여전히 오류가 났고, cnt를 쓰지않는 방법을 찾는 것이 효율적일 것 같다고 생각했다.
며칠간 풀었던 풀이를 보면 아이디어를 얻을 수 있지 않을까 싶어서, TIL을 돌아보았고 한가지 다른 점을 발견했다.
다른 문제들은 treenode형식이나 boolean으로 반환했는데, 이번 문제는 int형이라는 점이었다.
이런 식으로 바꿔주었는데
int형으로 반환이니 이 자체를 수를 센다고 생각하여 코드를 작성했다.
그런데 root의 left와 right를 쓸 수 가 없었다.
그래서 확인하느라 print(root)를 해보았고 결과는 사진과 같이 맞게 나왔다.
AttributeError: 'NoneType' object has no attribute 'left'
그럼 도대체 왜 이 오류는 해결이 안된단 말인가....!!! 하고 머리를 싸맸는데
이유는 간단했다.. 코드 순서가 잘못되었다.
node가 없을 때 조건을 가장 먼저 정의해줘야 했다..
순서를 바꾸고 해결되나 싶었지만
??? max연산이 안되는 것.. 이건 분명히 max에는 문제가 없다.. Nonetype이라는 것을 보니 아직도 노드가 없을 때 조건문에 문제가 있는 것 같다고 생각했다..
그러다가 떠오른 것.. int형이니까 return 0을 해야하나..?하고 혹시나 싶어 해보았는데
바로 해결되었다 ㅎ
사실은 간단한 문제때문에 헤매고 있었던 것이었다...
같은 유형의 다른 문제들을 연속해서 풀다보니 알고리즘이 확실히 좀 익숙해지는 것 같다.
기본적으로 머리속에서 바로 나오는 부분이 있으니 뿌듯했다.
여러 유형의 문제를 풀어보는 게 가장 도움되는 방법일 것 같다.
나는 일기형식으로 발생했던 오류들을 어떻게 해결했는지 위주로 적었는데, 내가 오류 해결법을 찾을 때마다 간추려 적혀있어 나와 그 오류가 같은 상황인지 정확치 않아 헤맸던 경험이 있었기 때문이다.. 누군가 나의 오류 해결법을 보고 도움을 받았길 바라며..!
풀이세션
return max(self.maxDepth(root.left,num+1),self.maxDepth(root.right,num+1)) if root else num미들러 분이 한줄 코딩 해주신 코드
좀 더 익숙해지면 간단하게 코딩하는 법도 연습해봐야겠다..!
