깊은바다거북
개발 공부 기록
깊은바다거북
전체 방문자
오늘
어제
  • 분류 전체보기 (219)
    • JAVA (9)
    • JavaScript (15)
    • 스파르타코딩클럽 (11)
      • [내일배움단] 웹개발 종합반 개발일지 (5)
      • [내일배움캠프] 프로젝트와 트러블 슈팅 (6)
    • SQL | NoSQL (4)
    • CS 등등 (0)
    • TIL | WIL (173)
    • 기타 에러 해결 (3)
    • 내 살 길 궁리 (4)

인기 글

최근 글

최근 댓글

태그

  • Til
  • TIT (Today I Troubleshot)
  • Backtracking(백트래킹)
  • 시간 복잡도
  • Preorder Traversal(전위 순회)
  • BFS(너비우선탐색)
  • Binary Tree(이진 트리)
  • 최소 힙(Min Heap)
  • Inorder Traversal(중위 순회)
  • leetcode-cli
  • 재귀 함수
  • 최대 힙(Max Heap)
  • Linked List
  • 자료 구조
  • 코딩테스트 연습문제
  • 팀 프로젝트
  • POST / GET 요청
  • tree
  • 자바스크립트 기초 문법
  • 01. 미니 프로젝트
  • DFS(깊이우선탐색)
  • 혼자 공부하는 자바스크립트
  • Trie
  • BST(이진 탐색 트리)
  • 점화식(Recurrence Relation)
  • 트러블 슈팅 Troubleshooting
  • 자잘한 에러 해결
  • TypeScript
  • Leetcode
  • 프로그래머스
hELLO · Designed By 정상우.
깊은바다거북

개발 공부 기록

TIL | WIL

9/29 (금) 순회 결과로부터 역으로 트리 구하기 TIL

2023. 9. 29. 22:14

공부한 것

  • LeetCode #105. Construct Binary Tree from Preorder and Inorder Traversal
    LeetCode - The World's Leading Online Programming Learning Platform
    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.
    https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

    이진 트리의 전위와 중위 순회 결과 배열을 가지고 역으로 원본 트리를 유추하는 문제다.

    진행중이고, 다음과 같이 생각해봤는데 이 쪽으로는 가망이 없는 것 같긴 하다:

    일단 같은 자리에 Pre[3,9], In[9,3]이렇게 순서만 바뀐 노드가 오는 때는 반드시 [3,9,null]의 부모-왼자식 관계가 확정된다.
    노드를 2개씩 짝지어 서브 트리를 그려 가능한 경우의 수를 짝지어 전체 트리를 그려봤지만 일관되게 설명하기엔 복잡하다.
    일단 preorder 배열의 연이은 두 값이 만들 수 있는 관계는 뒤의 값을 기준으로:
    1. 왼쪽 자식이 된다
    2. 외동 오른 자식이 된다
    3. 왼 형제가 있는 오른 형제가 된다
    의 세 가지가 가능하고, 
    inorder 배열의 연이은 두 값은 역시나 뒤의 값을 기준으로 앞의 값과의 관계가: 
    1. 오른 자식이 된다
    2. 왼 자식의 부모가 된다
    3. 오른 자식의 n대 왼 자손이 된다
    이렇게 세 가지가 가능하다.


서울 할머니 댁을 다녀와서 저녁 늦게 시작하여 푸는 시간이 부족했다. 그럼에도 불구하고 한 시간 가까이 생각했는데 이렇게 헤매고 있다니… 이 정도 문제는 40분, 20분 안에도 풀어야 한다고 알고리즘 풀이 책에서는 그러던데 알고리즘 문제를 푼 날 수가 꽤 됨에도 아직 이러고 있으니 조금 우울하다.


Uploaded by N2T

    'TIL | WIL' 카테고리의 다른 글
    • 10/11 (수) 브라우저에 막대 그룹 그래프를 그리다 TIL
    • 10/10 (화) 콘솔에 선 그래프를 그리다 TIL
    • 9/28 (목) leetcode-cli를 해부 중2 TIL
    • 9/27 (수) leetcode-cli를 해부 중 TIL
    깊은바다거북
    깊은바다거북

    티스토리툴바