1339. Maximum Product of Splitted Binary Tree

문제링크: https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/description/

이진 트리에서 노드 하나를 끊었을 때 두 트리 노드들의 합을 서로 곱했을 때 최대가 되는 결과를 구하는 문제다.

Solution

Postorder traversal

노드를 끊었을 때 이는 어떤 자식노드 - 부모노드 간의 연결을 끊는 것이 된다. 이때 부모로가는 연결이 끊긴 자식노드는 분리된 트리의 루트가 된다. 따라서 해당 노드를 루트로 하는 트리의 합을 구하면 분리된 노드의 총 합을 얻을 수 있고 나머지 트리의 합은 전체 합에서 빼면 구할 수 있다.

전체 합은 일정하고 일부분의 합을 구할 수 있을때 둘의 곱은 (totalSum - sum) * sum 이 된다. 이때 sum은 0.5totalSum에 근접할 수록 둘의 곱이 최대가 되는 점을 이용해 각 노드까지의 합 중 최적의 합을 구해 곱의 최대 크기를 얻을 수 있다.

Algorithm

• dfsSum으로 root노드부터 탐색한다.
• 현재 노드의 좌, 우 노드에서 dfsSum을 구한 후 node.val을 더해 현재 노드까지의 합을 구한다.
• 구한 값을 sum에 저장한다. (후위순회 순으로 저장된다.)
• 후위 순회이기 때문에 마지막으로 얻은 sum.at(-1)이 totalSum이 된다.
• 각 sum들을 탐색해 totalSum을 반으로 나눈 sumMiddle과 가장 가까운 차이를 구한다.
• mindDiff 를 통해 최대곱을 구하고 나머지 조건을 연산하고 반환한다.

var maxProduct = function(root) {
  // Postorder sum
  const sum = []; // Sum of each node (postorder)
  const dfsSum = (node) => {
    if (node === null) return 0;
    const nodeSum = node.val + dfsSum(node.left) + dfsSum(node.right);
    sum.push(nodeSum);
    return nodeSum;
  }
  dfsSum(root);
  const totalSum = sum.at(-1); // Last is root in postorder
  const sumMiddle = totalSum / 2;

  // Get sum nearest to sumMiddle
  let minDiff = Infinity;
  for (let el of sum) {
    minDiff = Math.min(Math.abs(el - sumMiddle), minDiff);
  }
  return ((sumMiddle + minDiff) * (sumMiddle - minDiff)) % 1000000007;

};

리트코드에서 처음으로 100%/100%의 결과를 냈다. 후위 순회로 각 노드를 탐색하기 위해 O(n)의 시간, O(logn)의 공간이 필요하다. 이후에 노드를 재탐색하면 추가 공간이 필요하지 않지만 동일한 덧셈 연산을 추가적으로 하고 싶지 않아서 sum배열을 통해 O(n)의 공간을 추가해 바로 minDiff를 연산할 수 있었다. 따라서 O(n)의 시간과 O(n)의 공간이 필요하다. maxProduct에 대한 연산을 직접 곱셈으로 찾지 않고 이차함수로 접근한 것이 연산에 약한 JS에서 큰 효과를 보인 것 같다.