Tree12 트리의 지름 트리의 지름은 트리의 노드들 중 가장 먼 거리를 가지는 두 노드 사이의 거리를 의미합니다. 알고리즘 1. 임의의 노드 x를 선택한다. 2. dfs로 x와 가장 먼 노드(A)를 구한다. 만약 가장 먼 노드가 2개 이상이라면 이들 중 어떠한 것을 선택해도 상관없다. 3. dfs를 한 번 더 돌려서, 노드 A로부터 가장 먼 노드(B)를 구한다. 4. 노드 A와 노드 B의 거리가 트리의 지름이 된다. 노드 사이의 거리인데 최단거리 알고리즘을 돌려야하지 않나?! 싶기도 하지만 "트리"의 지름을 구하고 있음을 유의해봅시다. 트리의 성질 중 "트리의 두 노드 사이의 경로는 하나만 존재한다."가 있습니다. 따라서 dfs 탐색 중에 구해지는 노드 사이의 거리가 최단거리가 됩니다. 참고코드 : github.com/fpdj.. 2021. 2. 21. [leetcode][116] Populating Next Right Pointers in Each Node 문제 : leetcode.com/problems/populating-next-right-pointers-in-each-node/ 같은 depth를 가진 노드들을 왼쪽에서부터 오른쪽 형제들을 각 노드들의 next 포인터로 연결한다. 노드들을 왼 -> 오 순으로 연결하기 때문에 노드들을 탐색하면서 왼쪽 자식, 오른쪽 자식 순으로 탐색해나간다. 같은 depth를 가진 노드들을 연결하기 때문에 depth를 key 값으로 하고 해당 depth들 중 가장 마지막에 탐색된 노드 포인터를 value 값으로 하는 map을 만든다. 탐색하면서 탐색 중인 노드의 depth로 가장 마지막 노드 정보를 가져와서 가져온 노드의 next 포인터에 현재 탐색 중인 노드 포인터를 넣는다. 그리고 value 를 현재 탐색중인 노드로 갱.. 2020. 11. 15. [leetcode][133] Clone Graph 문제 : leetcode.com/problems/clone-graph/ 모든 노드들이 연결된 방향성 없는 그래프가 주어진다. 이를 깊은 복사한 트리를 생성한 뒤 반환하라. 트리 노드부터 탐색해가면서 노드를 붙여나가는 BFS 방식으로 풀었다. 생성된 노드들에 대한 정보를 저장하기 위한 map 을 추가했다. 해당 map의 key는 node.val이 고유하다고 명시되어 있기 때문에 이를 사용하고 map의 value는 Node*을 저장한다. 탐색 중인 노드의 neighbors 들 중 생성되지 않은 노드가 있다면 생성한 뒤 map에 저장, 탐색 중인 노드의 clone 노드에 생성한 노드를 neighbors로 등록. 이미 생성된 노드라면 map에서 해당 노드를 가져온 뒤 clone 노드의 neighbors로 등록하.. 2020. 10. 21. [leetcode][979] Distribute Coins in Binary Tree 문제 : https://leetcode.com/problems/distribute-coins-in-binary-tree/ 루트에서 자식노드로 내려가면서 현재 탐색 중인 노드를 루트로 하는 서브트리의 모든 노드들이 코인을 하나씩 가지고 남는 코인개수를 반환한다. 이 함수를 getCoins라 한다면 수도코드는 다음과 같다. getCoins(root) = getCoins(root.left) + getCoins(root.right) + root.val - 1 root 노드의 val(가지고 있는 코인 개수)와 자식 노드들에게서 남는 코인개수를 가져와서 더해준다. 그리고 1을 빼준다. 이유는 root 노드도 1개의 코인을 가져야하기 때문에 root 몫의 코인 개수(1개)는 제외시켜야 하기 때문이다. 남는 코인개수를.. 2019. 12. 17. 트리 순회(전위 순회, 중위 순회, 후위 순회) 트리를 배우면 같이 배우게 되는 개념 중 하나죠. 트리 순회에 대해 알아보겠습니다. 트리 순회에는 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder) 가 있습니다. 텍스트 추가 [그림 1]은 예시로 그린 트리 입니다. 전위 순회는 [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회합니다. 중위 순회는 [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회합니다. 후위 순회는 [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회합니다. 이것만 안다면 차근차근 해나가면 됩니다. 일단 전위 순회입니다. 루트 - 왼쪽 - 오른쪽 순으로 순회한다면 결과는 CBAEDFG 가 됩니다. 개인적으로 제일 쉽다고 생각하는 순회방법입니다. 만약 잘 이해가 되지 않는다면 [그림 3]처럼 모든 .. 2019. 10. 4. [leetcode] 1028. Recover a Tree From Preorder Traversal 문제 : https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/ 탐색은 preorder로 왼쪽을 다채우고 부모노드로 올라가고 나서는 값을 채우기 위해 왼쪽 자식트리로 내려가지 않는다. TreeNode 구조체는 자식 노드의 정보만 담고 있으므로 부모노드를 저장하는 스택을 하나 만들었다. pair getValAndDepth(string& s) { if (s.size() == 0)return { -1, -1 }; int ind = 0; int val = 0; int depth = 0; for (; ind 0) { ind--; break; } else depth++; } else { val *= 10; val += s[ind] - '0'; }.. 2019. 4. 20. 이전 1 2 다음
