LeetCode 617 - Merge Two Binary Trees (Easy)

문제

LeetCode - 617번

풀이 과정

두 개의 이진 트리를 합치는 연산을 수행하는 문제입니다.

직관적으로 생각했을때는 쉬운거 같았는데 생각보다 어떤 방식으로 구현해야 명확할지 많은 고민을 했던 것 같습니다.

저는 merge 라는 함수를 재귀적으로 호출하여 문제를 해결하고자 했습니다.
우선 merge 의 기준이 되는 트리를 main, 나머지를 sub 로 나눈
다음 두 트리 모두 현재 루트 노드가 존재할 경우 main 에 값을 더했습니다.

다음 재귀호출 전에 먼저 서브트리가 존재하는지 확인하였고
두 트리 모두 각각 왼쪽 혹은 오른쪽 서브트리가 존재할때만 DFS 를 수행하고
그 외의 경우에는 별도의 처리를 해줬습니다.

여기서 별도의 처리란 main 의 왼쪽(오른쪽) 서브트리가 존재하지 않는데 sub 에 존재할 경우를 의미합니다.

마지막으로 merge 를 호출하는 첫 시점에서도 t1 과 t2 중에서
null 이 아닌 트리를 main 으로 설정해서 탐색을 수행하도록 했습니다.

코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} t1
 * @param {TreeNode} t2
 * @return {TreeNode}
 */
var mergeTrees = function (t1, t2) {
  function merge(main, sub) {
    if (main && sub) main.val += sub.val;

    if (main && main.left && sub && sub.left) {
      merge(main.left, sub.left);
    } else if (sub && sub.left) {
      main.left = sub.left;
    }

    if (main && main.right && sub && sub.right) {
      merge(main.right, sub.right);
    } else if (sub && sub.right) {
      main.right = sub.right;
    }
  }

  if (t1) merge(t1, t2);
  else merge(t2, t1);

  const ans = t1 ? t1 : t2;

  return ans;
};