계단을 올라갈 때 n번째까지 갈 수 있는 방법의 수를 물어보는 문제입니다.계단을 오를때 제한이 있는데 한 번에 1칸 또는 2칸씩 오를 수 있습니다. 이 뜻은 n번째 계단에 가기 위해서는 n-1번째 계단에서 1칸을 올라가거나 n-2번째 계단에서 2칸을 오를 수 있습니다.이를 쉽게 Recursion으로 풀 수 있습니다.  int climb(int n) { if (n == 0 || n == 1) // 안오르거나, 가장 첫 1칸 return 1; // 방법의 수는 1 // n번째 계단을 오르려면 n-1에서 한칸 또는 n-2에서 두 칸씩 오르면 된다 return climb(n - 1) + climb(n - 2); }(이 방..

이 문제는 트리를 좌우구조를 뒤집어주는 문제입니다.전체 트리 구조를 뒤집기위해 각각의 노드를 어떻게 해야할지 살펴보면 결국 각 노드의 왼쪽 자식과 오른쪽 자식 노드를 바꿔주면 됩니다.모든 노드의 자식 노드들을 바꿔줘야 하므로 DFS를 사용했습니다. Recursion/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * ..

이 문제는 트리가 두 개 주어집니다. 원래 트리의 구조 안에 서브 트리 구조와 같은 구조가 있는지 확인하는 문제입니다.만약 서브 트리 구조와 같은 구조가 있어도 추가적인 노드가 붙어있으면 같은 구조가 아닙니다. 서브 트리의 root 노드와 같은 노드가 나올때까지 자식 노드들을 타고 갑니다.만약 root 노드와 같은 노드를 찾았다면 그 구조가 같은지 확인해줍니다.  bool isSameStructure(TreeNode* main, TreeNode* sub) { if (!main || !sub) // 두 노드 중 하나만 nullptr이거나 모두 nullptr인 경우 return !main && !sub; // 두 노드 모두 nullptr인 경우엔 true 아니면 fals..

이진 트리가 주어지면 트리의 가장 큰 깊이값을 찾는 문제입니다.자식 노드로 계속 이동하며 깊이값을 찾는 문제이기에 DFS를 사용합니다. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),..

이진 트리가 주어지면 트리의 지름을 알아내는 문제입니다.트리의 지름은 한 노드에서 다른 노드로 가는 가장 긴 경로입니다.이 경로는 root노드를 지나갈 수도 있고 아닐 수도 있습니다. 만약 위의 예시와 같은 트리가 주어지면 가장 긴 경로는 노드 4에서 노드 3으로 가는 경로 혹은 노드 5에서 노드 3으로 가는 경로가 될 수 있습니다. 이는 노드 1의 왼쪽 자식의 최대 길이 + 오른쪽 자식의 최대 길이와 같은데 노드 1의 왼쪽 자식의 최대 길이는 2이고 오른쪽 자식의 최대 길이는 1로 트리의 지름은 3이 됩니다. 즉, 각 노드를 방문하며 노드의 왼쪽 자식의 최대 깊이와 오른쪽 자식의 최대 깊이를 더하면 그 노드를 root로 하는 subtree의 지름이 됩니다.이렇게 각 노드의 지름(Diameter)값을 비..

이진 트리 두 개가 주어졌을 때 트리들을 하나의 트리로 합치는 문제입니다.병합 규칙 :       1) 두 트리의 노드가 모두 존재하면 두 노드의 값을 합쳐 병합된 트리의 노드의 값으로 사용       2) 두 노드 중 null이 아닌 노드를 병합된 트리의 노드로 사용       3) 둘 다 null이면 nullptr /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(n..