리트코드

LeetCode 2196 Create Binary Tree From Descriptions 접근 map의 key에 node.val, value에 node reference 가 담긴다. 부모 노드는 p[child] = parent 의 방식으로 저장하여 루트를 찾는다. descriptions 를 훑으며 map 에 이미 저장된 child 가 있다면 해당 child 를 적절한 left or right 에 연결하고, child 가 map 에 없다면 새로운 노드를 만들어 연결한다. 사고 리스트로 풀어도 되고, 맵으로 풀어도 된다. 공간 덜 쓰고 root 찾는 방법이 있을것도 같다. map 을 안쓰고는 (node 들의 reference 를 다 붙잡고 있지 않고는) tree 만들 방법이 없는거겠지? ...

접근 기본적인 배경은 이분 탐색이다. 현재 pivot 기준으로 왼쪽을 봐야할지, 오른쪽을 봐야할지 조건을 생각하는 것이 관건이다. 만약 nums[low] <= nums[mid] 라면, 왼쪽 subarray 는 정렬되어있다. target 이 해당 range 를 벗어나면 오른쪽을 본다. 만약 nums[low] > nums[mid] 라면, 오른쪽 subarray 가 정렬되어있다. target 이 오른쪽 subarray 의 range 를 벗어나면 왼쪽을 본다. 사고 binary search 를 필요한 만큼 수정해서 직접 이용할 수 있는지 묻는 문제이다. 직접 sorting algorithm 을 구현하는 것보다는 개인적으로 쉽고 또 자주 직접 customizing 해야한다. 다양한 정렬 문제들을 Comparator 를 이용해서 접근하는 것처럼 binary search 또한 다른 상황에서 직접 필요한 부분을 수정해서 쓸 수 있도록 연습하자. ...