코테 스터디 23일차 TIL + 오늘의 학습 키워드 이진트리

- 오늘의 학습 키워드: 이진 트리

- 공부한 내용 본인의 언어로 정리하기

모든 노드에서 왼쪽 서브트리와 오른쪽 서브 트리의 높이 차이가 1이하인 트리

 

각 노드에서 왼쪽과 오른쪽 서브 트리의 높이 계산

높이 차이가 1보다 크면 균형이 안맞는거다

재귀적으로 모든 서브 트리가 균형이 맞는지 확인

 

직관적인 높이계산 수도코드

function isBalanced(root):
	if root is null;
    	return true(높이0)
        
    leftHight = getHeight(root.left)
    rightHight = getHeight(root.right)
    
    if abs(leftHeight - rightHeight) >1
    	return faluse
        
        return isBalanced(root.left) And is Balanced(root.right)
        
function getHeight(node)
	if node is null;
     	return 0
        
     return 1 + max(getHeight(node.left), getHeight(node.right))

 

최적화된 수도 코드

function isBalancedHelper(root);
	if root is null:
    	return [true,0] //isBalanced, height
        
    left = isBalancedHelper(root.left)
    right = isBalancedHelper(root.right)
    
    isBalanced = left[0] AND right [0] AND abs(left[1] - right[1]) <=1
    height =1 + max(left[1], right[1])
    
    return [isBalanced, height]
    
 function isBalanced(root):
 	return isBalancedHelper(root)[0]

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지
  - 어떻게 해결했는지
  - 무엇을 새롭게 알았는지
  - 내일 학습할 것은 무엇인지