[LeetCode] - 894_All Possible Full Binary Trees

문제 소개

• Medium / Dynamic Programming
• https://leetcode.com/problems/all-possible-full-binary-trees/description/

풀이

public List<TreeNode> allPossibleFBT(int n) {
    if (n%2 == 0) {
        return new ArrayList<>();
    }

    List<TreeNode> result = new ArrayList<>();

    if (n == 1) {
        result.add(new TreeNode(0));
    } else {
        for (int leftNodes = 1; leftNodes < n; leftNodes+=2) {
            int rightNodes = n-1-leftNodes;
            for (TreeNode left : allPossibleFBT(leftNodes)) {
                for (TreeNode right : allPossibleFBT(rightNodes)) {
                    TreeNode root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
            }
        }
    }

    return result;
}

이번 문제는 DFS로 풀어내야겠다는 생각은 들었지만, 그 이상으로 접근하기가 어려웠다.

그렇기에 내용을 풀어써보며 접근 방식에 대해 이해해보려고 한다.

• 각 노드의 하위 노드는 0개이거나 2개이므로 n이 홀수이며, 1보다 크다면 root 노드의 left, right는 항상 존재 한다.
  • 그렇기에 leftNodes는 1부터 n 까지 증가하며 경우의 수를 탐색한다.
  • 그 반대로 rightNodes는 n-1-leftNodes (n - root 노드 - left 노드의 개수) 가 된다.
• root의 하위 노드를 기준으로 left 노드의 개수, right 노드의 개수가 정한 후 위 방식을 계속 반복해나가면 된다.
• 아래 시뮬레이션에서는 n = 7일 떄의 상황을 생각해보며 작성 해보았고 너무 길어짐을 대비해 처음 leftNodes와 rightNodes의 상황만 다루었다.
  • leftNodes = 1 / rightNodes = 5
    • LEFT
      • leftNode의 개수는 1로 정해졌으므로 allPossibleFBT(leftNodes) 는 0 하나가 담긴 TreeNode를 return한다.
    • RIGHT
      • rightNode의 개수는 5로 정해졌으므로 allPossibleFBT(rightNodes) 는 아래와 같은 동작을 한다.
      • leftNodes = 1 / rightNodes = 3
        • LEFT
          • leftNode의 개수는 1로 정해졌으므로 allPossibleFBT(leftNodes) 는 0 하나가 담긴 TreeNode를 return한다.
        • RIGHT
          • rightNode의 개수는 3으로 정해졌으므로 allPossibleFBT(rightNodes) 는 아래와 같은 동작을 한다.
          • leftNodes = 1 / rightNodes = 1
            • LEFT
              • leftNode의 개수는 1로 정해졌으므로 allPossibleFBT(leftNodes) 는 0 하나가 담긴 TreeNode를 return한다.
            • RIGHT
              • rightNode의 개수는 1로 정해졌으므로 allPossibleFBT(rightNodes) 는 0 하나가 담긴 TreeNode를 return한다.
          • 하위 노드가 반환되면서 각 left, right에 할당되고 이를 result에 저장 후 return 한다.
        • 하위 노드가 반환되면서 각 left, right에 할당되고 이를 result에 저장 후 return 한다.
      • leftNodes = 3 / rightNodes = 1
        • LEFT
          • leftNode의 개수는 3으로 정해졌으므로 allPossibleFBT(leftNodes) 는 아래와 같은 동작을 한다.
            • leftNodes = 1 / rightNodes = 1
              • LEFT
                • leftNode의 개수는 1로 정해졌으므로 allPossibleFBT(leftNodes) 는 0 하나가 담긴 TreeNode를 return한다.
              • RIGHT
                • rightNode의 개수는 1로 정해졌으므로 allPossibleFBT(rightNodes) 는 0 하나가 담긴 TreeNode를 return한다.
          • 하위 노드가 반환되면서 각 left, right에 할당되고 이를 result에 저장한다.
        • RIGHT
          • rightNode의 개수는 1로 정해졌으므로 allPossibleFBT(rightNodes) 는 0 하나가 담긴 TreeNode를 return한다.
        • 하위 노드가 반환되면서 각 left, right에 할당되고 이를 result에 저장한다.
    • 하위 노드가 반환되면서 각 left, right에 할당되고 이를 result에 저장한다.
    • 위 과정에서 2개의 트리노드가 완성되어 저장된다.
  • leftNodes = 3 / rightNodes = 3
    • 이하 생략
    • 위 과정에서 1개의 트리노드가 완성되어 저장된다.
  • leftNodes = 5 / rightNodes = 1
    • 이하 생략
    • 위 과정에서 2개의 트리노드가 완성되어 저장된다.

 

그래서 이 문제가 왜 동적계획법인가?

동적계획법은 큰 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘임을 알고 있었다.

하지만 그걸 감안해서 봐도 DFS 문제로 느껴져서 참 난감했다.

그렇기에 이 문제가 왜 DP인지 알아보자.

• 중복되는 하위 문제
  • 위에서 알 수 있다시피 leftNodes = 1 / rightNodes = 5 일 때, leftNodes = 5 / rightNodes = 1일 때 하위에서 발생하는 문제는 동일하다.
• DP는 이전의 결과를 메모이제이션을 통해 저장하고 재사용함으로써 중복 계산을 피해야한다.

그렇기에 위의 코드는 단순히 DFS만 활용해서 DFS 문제로 느껴진 것이었고, DP 문제로써 풀어나가려면 아래와 같이 메모이제이션을 이용해야한다.

private static Map<Integer, List<TreeNode>> memoization = new HashMap<>();

public List<TreeNode> allPossibleFBT(int n) {
    if (n%2 == 0) {
        return new ArrayList<>();
    }
    if (memoization.containsKey(n)) {
        return memoization.get(n);
    }

    List<TreeNode> result = new ArrayList<>();

    if (n == 1) {
        result.add(new TreeNode(0));
    } else {
        for (int leftNodes = 1; leftNodes < n; leftNodes+=2) {
            int rightNodes = n-1-leftNodes;
            for (TreeNode left : allPossibleFBT(leftNodes)) {
                for (TreeNode right : allPossibleFBT(rightNodes)) {
                    TreeNode root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
            }
        }
    }

    memoization.put(n, result);
    return result;
}

 

위와 같이 메모이제이션을 적용하여 이번 문제의 수행속도를 줄일 수 있게 되었다.

적용 전 / 적용 후