LCA는 Lowest Common Ancestor인 노드를 뜻한다. input으로는 조건이 되는 두개의 노드와 함께 트리가 들어온다. 간단한 트리 재귀문제였다. root가 조건 p,q를 만족할때 리턴해주고, 해당 노드의 left, right를 각각 재귀로 돌려주면된다. 최종적으로 left에 p,q가 없다면 right를, right에 없다면 left를 리턴해주고, 둘 다 있다면 다시 root를 리턴해주면 된다.

트리에서 특정 sum을 만들어 낼 수 있는 연속된 부분집합을 찾아라 약간 헷갈렸는데, dfs와 재귀를 별개로 사용하면 된다. 하나의 노드에서 dfs를 실행하는데, 그게 모든 node가 root가 되어 실행되어야 한다. 그렇기 때문에 dfs는 원래대로 해준다. 이때 오해하지 말아야 할 점이, 같은 root에서 시작한다고 하더라도 조건을 만족하는 답은 여러개 있을수 있으므로, left와 right를 leaf까지 dfs돌려줘야 한다. 최종적으로는 특정 root를 기준으로 나온 count들을 전부 합하면 된다.

node가 집이고 도둑이 여기를 순회하면서 node의 value만큼 돈을 훔친다. 이때 바로 옆집을 훔치면 경찰에 잡혀서, 한칸이상 떨어진 집의 돈을 훔쳐야 할 때, 총 얼마나 훔칠 수 있는지 구하라는 문제 하나의 node에 방문했을 때, 그 node의 집을 훔치기로 한다면 r, 아니라면 n이라고 하자 leaf라면 [0,0]이 되겠지만, 그것이 아니라면 [ 훔치기로 함, 안훔치기로 함]이 된다 훔치기로 하면 그 node의 value를 리턴해주면 된다. 안훔치기로 했으면 그 아래 노드의 최댓값을 리턴해준다

tree가 valid한지 판단하라는 것인데, 이 트리의 valid함은 left, right 트리가 크기대로 잘 정렬되어있냐의 여부이다 경계값을 제거하고, helper함수에 대해 root가 min보다 작은 value를 가졌거나, max보다 큰 value를 가진 경우에 false를 리턴해주면 된다.

inorder traversal와 preorder traversal한 데이터가 들어왔을때 트리를 그리라는 뜻 간단하게 정리하자면 Preorder는 root->left->right 순으로 순회를, Inorder는 left->root->right 순으로 순회를 하는 것이다. 각 traversal 결과에 대해 root를 기준으로 정리할 수 있다. 예컨데 preorder의 경우 root node를 가장 먼저 방문하므로, 3이 root가 되고 이를 inorder에 적용하면 3을 기준으로 9가 left node, 15,20,7은 right node라는 것을 알 수 있다. 따라서 다음과 같은 방식으로 문제를 풀어보려 한다 helper라는 함수를 이용하여 재귀처리 하려고 한다. 이때 사용되는 args는 rootPreI..

트리가 주어지면 이를 Linked-List로 바꾸는 문제이다. 조건에 따라 right node는 next node가 되고, previous는 null이 된다. convertToList라는 함수를 제외하고 보자. Tree니까 재귀를 떠올리고. root가 주어지면, root의 left와 right를 flat하게 만든 후, null- root - left subtree - right subtree 형태로 붙이면된다. 이때 left와 right의 관계를 재귀로 처리해준다. 이제 convertToList를 살펴보면, right가 있는 경우, left.right가 null이 될대까지 모든 left node를 거슬러 내려간다 예컨데 left의 node가 3개라면, first.right는 Loop가 세번 돌아야 존재할..