분류 전체보기12 8. Maximum Depth of Binary Tree 방법 1 (내가 한 거): 주어진 트리의 높이를 찾는 문제이다. 나는 depth별로 노드를 방문하는 DFS(pre-order)를 활용했다. 그리하여 각 층에 존재하는 노드를 방문할 때마다 높이 값을 1 늘려주었다. 그 후 그 값들을 vector에 저장하여 최댓값을 찾아냈다. 1. Pre-order traversal을 할 수 있게 기본 틀을 작성한다. 2. 노드를 방문하면 height 값을 1 늘려주고 벡터에 그 값을 넣는다. 3. 트리에 있는 모든 노드들을 다 훑었다면 벡터 속 최댓값을 찾는다. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNod.. 2023. 2. 12. 7. Symmetric Tree 주어진 트리가 좌우대칭을 이루는지 확인하는 문제이다. 왼쪽과 오른쪽의 대칭성을 확인해야 하기 때문에 노드 2개를 이용해 하나는 왼쪽 하나는 오른쪽의 트리를 훑게 했다. 그리하여 두 노드가 같은 값을 가지는지 확인하였다. 1. 노드 2개를 파라미터로 받는 recursive function을 생성한다. 2. 서로 대칭이 되게 이동해야 하니 하나가 왼쪽으로 이동한다면 다른 하나는 오른쪽으로 이동하게끔 다시 파라미터 안에 집어넣는다. 3. base case를 설정한다 - 두 노드가 NULL, 즉 false를 리턴하지 않고 leaf node에 달성하게 된다면 true를 리턴한다 / 둘 중 하나만 NULL에 도달한다면 false를 리턴한다 / 두 노드의 값이 다르면 false를 리턴한다. /** * Definiti.. 2023. 2. 12. 6. Binary Tree Inorder Traversal Binary tree를 활용해야 하는 문제이다. Tree에 있는 노드를 inorder traversal로 정렬하여하는 문제이다. 1. 만약 root가 NULL이 아니라면 stack에 쌓고 root를 왼쪽으로 이동시킨다. 2. 만약 root가 NULL이라면 stack 맨 위에 위치한 노드를 root로 설정한 뒤 res 벡터에 이동시킨다(print). 3. stack이 비고 root가 NULL일 때 까지 이 과정을 계속 반복한다. Time complexity: O(n) Space complexity: O(n) /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * T.. 2023. 1. 29. 5. Climbing Stairs n개의 계단을 1개 또는 2개의 스텝으로만 오를 수 있다. 이때, n개의 계단을 오를 수 있는 경우의 수를 구하는 문제이다. 처음에는 combination을 활용해 접근하였다. (n-n/2)C(n/2)의 식에 n을 대입하는 방식으로 답을 구하려 했지만 조합의 값을 구하기 위해서는 팩토리얼을 사용해야만 한다. 즉, n의 값이 20만 넘어가도 수가 어마어마하게 커진다. long long unsigned int를 활용해도 이 수를 담아내지 못한다. class Solution { public: long long int fact(int n) { if (n == 0 || n == 1) return 1; else return n * fact(n - 1); } int comb(int n, int r){ return f.. 2023. 1. 5. 이전 1 2 3 다음
