894. All Possible Full Binary Trees

894. All Possible Full Binary Trees

https://leetcode.com/problems/all-possible-full-binary-trees/

문제

풀이

위에 그림에서 알 수 있드시
dfs(3) => [1,1]
dfs(5) => [1,3], [3,1]
dfs(7) => [1,5], [3,3], [5,1]이 된다.
dfs(3) = [1,1]로 리턴을 하게 된다면 dfs(5) = [1, [1, 1]], [[1, 1], 1]이 될 것이고 dfs(5)도 리턴을 하게된다면 dfs(7) = [1, [1, [1, 1]]] or [1, [[1, 1], 1]] or [[1, 1], [1, 1]] or [[1, [1, 1]], 1] or [[[1, 1], 1], 1]이 될 것이다.

1. dfs(1)일 때에는 [TreeNode(0)]을 리턴할 것이고
2. dfs(3)일 때에는 [1,1]인 트리노드를 리턴할 것이고
3. dfs(5)일 때에는 [1, [1,1]]인 트리노드와 [[1,1], 1]인 트리노드를 리턴할 것이다. 이런식으로 해서 left, right변수에 트리노드 경우의 수를 나타내고 append후 리턴하는 방식이다.

느낀점

알고나니 쉽지만 몰랐을 때에는 어려운 문제였다. 계속해서 반복학습 해야겠다.