[leetCode] 617. Merge Two Binary Trees

🚀 Description

You are given two binary trees root1 and root2.

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 the two trees 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 the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

Example 1:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Example 2:

Input: root1 = [1], root2 = [1,2]
Output: [2,2]

🚀 Solution

DFS

solution안의 definition등등을 문제 풀 때 잘 보자.

/**
 * 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} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function(root1, root2) {
    if (root1 && root2) {
        root1.val = root1.val + root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
    }
    if (root1 !== null && root2 === null) {
        return root1
    }
    if (root1 === null && root2 !== null) {
        return root2
    }
    return root1
};

1. 먼저 시작 노드의 값을 합친 뒤, 왼쪽 오른쪽으로 각각 이동하며 mergeTrees함수를 재귀호출한다.
   이동하며 해당 이동한 노드를 각각 합친다.
2. 중요한 점은 null값이 있는 노드의 경우 null값이 아닌 노드의 값으로 합쳐지기 때문에, 조건문을 작성해주어야 한다. 한쪽만 null값인 경우 null이 아닌 값의 노드를 리턴한다.

🚀 Result

Runtime

116 ms, faster than 55.12% of JavaScript online submissions for Merge Two Binary Trees.

Memory Usage

46.4 MB, less than 85.39% of JavaScript online submissions for Merge Two Binary Trees.