894. All Possible Full Binary Trees

[antop-dev]

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

[antop-dev]

양쪽(left, right)의 상위에 노드를 하나 더하면서 이진 트리를 완성해 나간다

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun allPossibleFBT(n: Int): List<TreeNode?> {
        if (n == 0) return listOf()
        if (n == 1) return listOf(TreeNode(0))

        val list = mutableListOf<TreeNode?>()
        for (left in 1 until n step 2) {
            val right = n - left - 1
            for (l in allPossibleFBT(left)) {
                for (r in allPossibleFBT(right)) {
                    val parent = TreeNode(0).apply {
                        this.left = l
                        this.right = r
                    }
                    list.add(parent)
                }
            }
        }
        return list
    }
}

팩토리얼과 비슷하게 중복된 연산이 엄청 많다. 이 부분은 메모제이션 하면 좋아질 것이다.

[antop-dev]

n이 짝수일 때는 아예 처리를 안하도록 한다.

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun allPossibleFBT(n: Int): List<TreeNode?> {
        if (n % 2 == 0) return listOf()
        if (n == 1) return listOf(TreeNode(0))

        val list = mutableListOf<TreeNode?>()
        for (left in 1 until n step 2) {
            val right = n - left - 1
            for (l in allPossibleFBT(left)) {
                for (r in allPossibleFBT(right)) {
                    val parent = TreeNode(0).apply {
                        this.left = l
                        this.right = r
                    }
                    list.add(parent)
                }
            }
        }
        return list
    }
}