n개의 노드가 주어졌을때 만들수 있는 BST의 조합 갯수를 구하는 문제이다. Tree의 전형적인 재귀방식으로도 풀 수 있으나, 기본적으론 DP로 풀어낼 수 있다. BTS는 크기에 따라 자연스레 노드가 배치된다. 그러니까 root node만 배치하고 갯수만 나누어주면, 각각의 경우의 수는 고정된다는 뜻이다. 예컨데 다음과 같이 세개의 원소가 주어진다고 해보자. 만약 특정원소를 root로 정한다면, 양옆에 BST를 만들 수 있는 경우의 수는(2개,0개) (1개,1개) (0개,2개)로 나누어지는 방식일것이다. 예컨데 n개의 원소가 존재하고, f(n) 을 n개로 만들 수 있는 BST의 수라고 한다면 f(n) =( f(n)*f(0) ) + ( f(n-1)*f(1) ) + ( f(n-2)*f(2) ) + ( f(n..

right 노드들만 배열로 만들어 리턴하라는 문제다 BST에서 right노드는 부모노드보다 큰 value를 가진 애들일테다 처음엔 이렇게 간단한 로직만 생각했었는데, level을 고려하지 못했다는 사실을 깨달았다 이전 level에 따른 traverse와 동일하게 args를 설정하면 된다 새로운 level에 도달하면 일단 node의 value를 넣어주되, right node가 있는 경우에는 right node의 value를 push 없다면 left node를 push하는 것으로 설정한다 이러한 조건은 level과 length가 같은지를 체크함으로 설정한다 right node의 value가 이미 들어왔다면 해당 조건을 만족하지 못하므로 별도의 node입력 없이 끝날것이기 때문

트리를 traverse해서 level(delpth)가 같은 노드끼리 묶어 리턴하라 트리 traverse이니 역시나 재귀를 활용할텐데, 여기엔 'result 배열의 length는 depth와 같아야 한다.'는 조건이 있다 따라서 함수는 result의 length와 depth가 다르다면 빈 배열 원소를 만들어주고, 해당하는 노드의 value를 push하도록 설계해야 한다. 이렇게 말이다. 단, 모든 경우는 root가 있는 경우다. 또한 재귀의 경우는 다음 node로 넘어갈때 재귀를 돌리는 것이므로 level에 1을 더해준다.

Tree와 index k 가 주어졌을때 k번째로 작은 node는 무엇인지 구하라는 문제 간단한 DFS문제이다 DFS순서에 따라 이진트리의 value를 정렬하면 내림차순으로 정렬된다

그냥 순서대로 Tree를 Traverse하기 으레 그렇듯 Tree 문제는 recursion을 먼저 떠올리면 된다. result 배열을 만들고, traverse 함수를 정의한다. traverse함수는 각각 left와 right노드에 대해 recursion을 실행하고, value를 result에 차곡차곡 담는다. 단 주의할부분은 traverse이므로 left노드 -> root 노드-> right노드 순으로 순회해야 한다는 점이다.

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 트리가 symmetric한지 여부를 살피는 문제 트리는 항상 재귀를 사용한다는 점을 기억하자