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

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

 

Lowest Common Ancestor of a Binary Search Tree
- 공부한 내용 본인의 언어로 정리하기

이진트리에서 두 노드 p와 q의 최소 공통 조상 찾기

lca는 두 노드를 모두 자손으로 가지는 가장 낮은 노드

이진 탐색 트리에서 모든 왼쪽 자식노드는 부모보다 작고 모든 오른쪽 자식노드는 부모보다 크다.

p와 q의 값이 현재 노드보다 모두 크면 LCA는 오른쪽 서브트리에 있고

p와 q의 값이 현재 노드보다 모두 작을때 LCA는 왼쪽 서브트리에 있다.

 

수도 코드

함수 lowestCommonAncestor(root, p ,q)
  현재 = root.val
  p값= p.val
  q값= q.val
  
  만약 p값> 현재 그리고 q값> 현재:
    오른쪽 서브트리에서 lca 찾기
    return lowestCommonAncestor(root.right, p,q)
    만약 p값 < 현재 그리고 q값이 <현재:
      왼쪽 서브트리에서 lca 찾기
      return lowestCommonAncestor (root.left, p,q)
      
      그외
      현재 노드가 lca일때
        return root

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

  - 어떻게 해결했는지

gpt랑 같이 풀었따.
  - 무엇을 새롭게 알았는지

가장 가까운 조상 노드 찾기 아예 개념 모르고있었다. 이진 탐색 트리에서 모든 왼쪽 자식노드는 부모보다 작고 모든 오른쪽 자식노드는 부모보다 크다. 는 것도 이번 문제로 새롭게 배웠따.
  - 내일 학습할 것은 무엇인지