[일일 리코드] 110. - 두 갈래 나무가 밸런스인지 아닌지 판단.
10791 단어 매일 리코드
제목 링크 여기.
기사 목록
제목 설명
두 갈래 나무를 정해 고도의 균형을 이루는 두 갈래 나무인지 아닌지를 판단한다.
본고에서 한 그루의 고도 균형 두 갈래 나무는 한 그루의 두 갈래 나무의 각 노드의 좌우 두 개의 하위 나무의 높이 차이의 절대치가 1을 초과하지 않는다고 정의한다.
예 1:
두 갈래 나무[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
true로 돌아갑니다.
예 2:
두 갈래 나무[1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
false로 돌아갑니다.
문제 풀이 사고방식
제목에는 넓이 우선(BFS) 방식으로 표시된 두 갈래 나무가 있지만 뿌리 노드의 주소만 알면 온전한 나무를 대표할 수 있다.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
그래서 제목은 뿌리 노드에서 착안하여 두 갈래 나무가 균형 있는 두 갈래 나무인지 아닌지를 판단할 수 밖에 없다.
모든 자목이 균형을 잡아야 하기 때문에 비교적 자연스럽게 귀속을 이용하여 뿌리 노드부터 층층이 아래로 내려가는 것을 생각한다.어떤 노드의 좌우 나무가 균형을 이루고 깊이의 차이가 1을 넘지 않으면 이 노드가 대표하는 나무가 균형을 이루고 그 결과를 순서대로 합친다.
이곳은 자목의 깊이를 직접 얻을 수 없으며, 가장 먼저 떠오르는 것도 또 다른 귀속을 이용하는 것이다.그래서 아래의 초기 답이 나왔습니다.
초기 답안
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def getDepth(node):
if not node:
return 0
else:
left = getDepth(node.left)
right = getDepth(node.right)
return max(left,right)+1
if root:
left = getDepth(root.left)
right = getDepth(root.right)
if abs(left-right)<2:
return self.isBalanced(root.left) and self.isBalanced(root.right)
else:
return False
else:
return True
이곳의 임시 함수
getDepth()는 깊이를 얻기 위해 좌우 양쪽 트리 깊이의 최대값에 1을 더하면 된다.반면에 귀속을 끝내는 조건은 전입된 노드가 None, 즉 잎 노드의 좌우 서브 노드로 바로 0으로 되돌아오는 것이다.isBalanced() 함수가 하나의 노드에 전입된 실례는 전입된 노드가 None일 때도 마찬가지다.이 답안은 확실히 정확하지만 집행 효율은 매우 떨어진다.실행 시간: 104ms, 제출 5.68%만 격파.
시간의 복잡도를 계산해 보다.여기에는 두 층의 귀속과 관련된다. 주 함수는 모든 노드를 한 번 훑어봐야 하고, 모든 노드는 내부의 귀속을 한 번 실행하며, 이 노드의 모든 하위 노드를 훑어봐야 한다.그래서 최악의 경우 전체 횟수는
(N-1)+(N-3)+(N-7)+...(N-M)로 모두logN층이 있기 때문에logN개의 소괄호가 있다.시간 복잡도는 O(NlogN)입니다.답안 개선
한 그루의 나무가 균형을 이루지 못하면 전체 나무가 균형을 이루지 못하기 때문에 사실 깊이를 얻을 때 바로 아래에서 위로 판단할 수 있다.귀속을 진행하여 깊이를 얻을 때 임의의 노드가 불균형적이면 하나의 표지 위치로 되돌아와 전달하면 나무 전체가 불균형적이다.이렇게 하면 밑에 나무의 불균형이 있다는 것을 뻔히 알면서도 뿌리 노드를 기다려야만 최후의 판단을 할 수 있다.
깊이와 판단의 균형을 맞추어 진행된 이상 귀속 하나만으로도 충분하다.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def getDepth(node):
if not node:
return 0
else:
left = getDepth(node.left)
right = getDepth(node.right)
if left == -1 or right == -1:
return -1
elif abs(left-right)<2:
return max(left,right)+1
else:
return -1
if root:
if getDepth(root) == -1:
return False
else:
return True
else:
return True
만약에 자수의 불균형이 있다면 바로 -1로 돌아가고, 귀속할 때 좌우 자수가 하나만 돌아오면 -1의 마지막 결과는 -1, 즉 불균형이다.그래서 최악의 상황은 뿌리 노드에 이르러서야 판단되는 것이다. 즉, 모든 노드를 두루 훑어보는 것이다.시간 복잡도는 O(N)입니다.
다시 제출, 실행 시: 68ms, 61.27%의 제출을 이겼습니다.확실히 많이 늘었어.
주의사항
이 문제를 쓸 때 처음에는
getDepth() 를 정적 방법으로 정의하고 실례 방법에서 직접 사용하려고 했는데 안 된다는 것을 발견했다.보아하니 내가 이전에 클래스 안의 정적 방법에 대해 약간의 오해를 한 것 같다. 정적 방법은 실례나 클래스에서만 호출될 수 있지만 더 이상 클래스가 정의한 내부에서 호출될 수 없다.따라서 클래스 내부에서 임시 함수를 호출하려면 실례적인 방법으로 정의하는 것이 좋습니다. 그리고 이름 앞에 두 개의 밑줄을 쳐서 내부에서만 사용할 수 있습니다.나는 평생 공부하는 인터넷 종사자인 T형 소액 결제원이다.제 블로그를 좋아해서 csdn에서 저를 팔로우해 주신 것을 환영합니다. 문제가 있으면 아래의 평론 구역에서 교류해 주십시오. 감사합니다.
좋은 웹페이지 즐겨찾기
