143. Reorder List

Complexities 📈

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Explanation 📝

기존 리스트	수정해야할 리스트

처음에는 하나의 메서드를 활용해서 재귀로 돌릴 수 있을까 고민했지만 아직 제 머리로는 명확하게 구상하지 못해 while문과 for문을 이용하여 풀이했습니다.
위 그림처럼 각 노드의 next를 달팽이처럼 연결지어줘야하기 때문에, head부터 tail까지를 반복하며 리스트에 넣어주었습니다.
그 뒤, 리스트에 들어간 각 노드들을 index로 접근하여 next에 값을 알맞게 수정해주었습니다.
이렇게 next를 설정하다보면 마지막에 자기 자신을 참조하게 되는 경우가 발생하는데, 조건식을 통해 자기 자신으로 할당이 될 경우를 판단하여 null로 설정해주었습니다.
홀수인 경우에는 반복문에서 따로 처리되지 않기 때문에 추가로 next를 null로 설정해주는 코드를 넣었습니다.

• 143. Reorder List - Test code

19. Remove Nth Node From End of List

Complexities 📈

• Time Complexity: $O(c)$ (c = node의 수)
• Space Complexity: $O(1)$

Explanation 📝

처음에는 Space Complexity가 $O(c)$ (c = node의 수)로 동작하는 코드로 구현했으나, n만큼 먼저 이동한 노드와, head를 가리키는 노드와 함께 하나씩 next를 통해 반복함으로써 기존에 이동했던 노드가 nil을 발견하게 될 경우 나중에 방문하기 시작했던 노드는 끝에서 n번째를 가리키는 것을 확인했습니다. 이를 통해 $O(1)$로 풀이할 수 있었습니다.

• 19. Remove Nth Node From End of List - Test code

235. Lowest Common Ancestor of a Binary Search Tree

Complexities 📈

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

Explanation 📝

처음에는 부모자식관계로서만 파악했으나, 나아가 조부모 그 이상의 관계가 될 수 있다는 것을 미처 파악하지 못했었습니다.
그래서 root 노드와 p, q가 동일하다면 해당 노드를 리턴해주고, 그게 아니라면 root노드의 자식노드로 재귀를 돌렸습니다.
그 이후 left와 right가 전부 값이 존재하다면 root노드를 리턴하고, 한 쪽에 치우쳐져있다면, 해당 값을 그대로 리턴하는 식으로 구현했습니다.

마침 Valid BST가 기준노드의 왼쪽 숫자는 기준 노드의 수보다 작고, 오른쪽 노드들의 숫자는 기준 노드보다 크다는 점에 착안하여 문제 풀이를 변경했습니다.

• 235. Lowest Common Ancestor of a Binary Search Tree - Test code

102. Binary Tree Level Order Traversal

Complexities 📈

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Explanation 📝

Swift는 Queue가 없어서 Linked-List로 구현했습니다.(사실 트리의 길이가 그렇게 길지 않아서 Array를 이용한 풀이도 좋긴 합니다.)
Root노드와 가상의 layer계층을 고려하여 Queue에 노드와 Int타입의 layer를 푸시 및 팝 하는 방식으로 구현했습니다.

• 102. Binary Tree Level Order Traversal - Test code

98. Validate Binary Search Tree

Complexities 📈

• Time Complexity: $O(n)$
• Space Complexity: $O(log n)$

Explanation 📝

재귀를 이용하여 풀이했습니다. left를 우선 검증한 다음, 오른쪽을 탐색했고, 추적을위한 이전 노드를 별도로 구성하여 서로 비교하도록 구현했습니다.

• 98. Validate Binary Search Tree - Test code