[Tree] Unique Binary Search Trees II

오늘 아침부터 지금 두 문제 각 잡았다.

뭔가 둘 다 비슷해보여서 .. 이름도 비슷하고 ..

사실 지금 포스팅하는거는 며칠 전에 했는데 내 것으로 하기까지 시간이 걸렸다.

(어떤 분 것을 참고해 그냥 외웠다 .. 큰일이다 ..)

근데 만약 알고리즘 쉬면 못풀거같긴하다 ..

 

이진트리인데 순서에 상관없이 나열하라는 듯 하다

 

public List<TreeNode> generateTrees(int n) {
	return DFS(1, n);
}

public List<TreeNode> DFS(int start, int end) {
	List<TreeNode> answer = new ArrayList<>();
	if (start > end) {
		answer.add(null);
		return answer;
	}
	if (start == end) {
		answer.add(new TreeNode(start));
		return answer;
	}
	List<TreeNode> lt, rt;
	for (int i=start; i<=end; i++) {
		lt = DFS(start, i-1);
		rt = DFS(i+1, end);
		for (TreeNode x : lt) {
			for (TreeNode y : rt) {
				TreeNode tn = new TreeNode(i);
				tn.left = x;
				tn.right = y;
				answer.add(tn);
			}
		}
	}
	return answer;
}