[Tree] Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

 

 

두개의 바이너리 트리에 node 두 개가 들어올때

겹치는 부분의 value는 증가, 둘다 없을 때는 비어있는 노드가 되는 경우다

즉, t1, t2가 둘 다 있으면 합쳐져서 노드가 되고, 하나만 있으면 그대로 던지면 된다

 

 

일종의 DFS이다. 

따라서 기본적으로 recursion이 일어나고 모든 노드를 방문하게 된다

(다만 방문을 표기하진 않는다)