2020.08.24 Merge Two Binary Trees 풀이

문제 ) 두 개의 binary trees가 주어질때, 같은 위치의 노드의 합을 더해 새로운 binary tree를 만드는 것이다. 

해결) 나는 너무 어렵게 접근했나보다. 해답은 생각보다 간단했다. (문제 풀때 너무 많은 시간이 걸리면, 그냥 답을 보고 익힌다. 수학의 정석 문제처럼, 알고리즘도 결국엔 같은 패턴이 있다고 생각하여 초반에 모르는 건 그냥 답을 보고 해결하는 방법에 익숙해지려고 노력한다)

 

/**
 * 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) {
  if(t1 === null) {
    return t2
  }
  if(t2 === null) {
    return t1
  }
 
  t1.val += t2.val
  t1.left = mergeTrees(t1.left, t2.left)
  t1.right = mergeTrees(t1.right, t2.right)
  return t1
};

 

재귀를 이용해서 각각의 좌우 노드를 돌며 끝난다. 재귀는 언제나 무한정 돌지 않도록 exit 가 있어야 하는데, 해당 풀이에서 t1 === null 과 t2 === null 부분이 탈출구다. 나는 헬퍼 함수까지 만들어서 new TreeNode를 새로 생성해 만드려고 했는데, 그냥 t1에 머지 시키면 되는 거였다. 문제 그대로 기존의 t1에 합치는 문제. 만약 이 문제를 면접에서 보게 되서 새롭게 생성해야되는지, 기존 노드에 합쳐도 되는지 궁금하다면 문제를 보기 전 질문해야겠다. 오늘은 어렵지 않은 걸 풀고 싶어서 68%의 정답률을 자랑하는 문제를 골랐는데.. 풀지 못했다..! 나중에 100문제 다 풀고 나서 이 문제를 보았을 때 쉽게 풀 수 있었으면 좋겠다! 

 

https://leetcode.com/problems/merge-two-binary-trees/solution/

Merge Two Binary Trees - LeetCode