[LeetCode] 617. Merge Two Binary Trees - 문제풀이

Description

두개의 이진트리를 병합하는 문제입니다. DFS와 유사하게 해결 할 수 있습니다.

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]

Constraints:

• The number of nodes in both trees is in the range [0, 2000].
• 104 <= Node.val <= 104

Solution 1. 전위 순회(pre-order) 재귀 호출

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {

    if (t1 == null && t2 == null) {
        return null;
    } else if (t1 == null){ // 한쪽 노드만 남아있으면 그대로 붙임(하위 노드들도 더이상 머지를 안해도 되기때문에 그대로)
        return t2;
    } else if (t2 == null){ // 한쪽 노드만 남아있으면 그대로 붙임
        return t1;
    } else{  // 양쪽다 노드가 있는 케이스
        // 머지된 신규 노드 생성
        TreeNode tree = new TreeNode(t1.val+t2.val);
        // DFS 알고리즘과 유사하게 전위 순회(pre-order Traversal)로 진행. 재귀로 자식노드가 끝까지 가서  null이 나오면 재귀호출 스택을 쭉 타고 올라와서 루트까지 머지된 노드를 반환한다
        tree.left = mergeTrees(t1.left, t2.left);        // left
        tree.right = mergeTrees(t1.right, t2.right);     // right
        return tree;
    }
}

깊이우선탐색(DFS) 알고리즘과 유사하게 전위 순회(pre-order Traversal)로 진행하며 재귀 호출로 루트 > 왼쪽 > 오른쪽 순서로 진행하며 머지해 나갑니다.

• 시간 복잡도: O(M). 두 트리의 최소 노드 수
• 공간 복잡도: O(M). 두 트리의 최소 노드 수

Reference

Merge Two Binary Trees - LeetCode