[LeetCode]617. Merge Two Binary Trees (python, java)

Merge Two Binary Trees - LeetCode

두 이진트리 root1, root2가 주어졌을 때 , 둘을 머지하는데 머지규칙은

• 만약 두 노드가 겹친다면 → 두 노드이 합을 새로운 노드의 값으로 한다.
• Otherwise → null 이 아닌 노드들을 사용한다.
• merging process는, 두 트리의 root node부터 시작해야함.

문제 풀이 (java)

(17)

root에서부터 시작해서 순서대로 만들면 될 것 같다.

• t1 에는 left가 없고 t2에는 left가 있으면 → t2의 left subtree를 그대로 붙이면 됨 .
• dfs를 사용해서 위→아래로 내려가며 노드를 덧 붙일 경우, root1 트리, root2 트리, 새로운 트리 세개의 인자를 매 번 전달 하는 방식을 취했음.

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1; 
        // 새로운 트리의 root 값 
        TreeNode tree = new TreeNode(root1.val + root2.val);
          
        dfs(root1,root2,tree);
        
        return tree; 
        
    }
    // 새로운 트리의 root에서부터 시작하여, left, right를 찾는다 
    public void dfs(TreeNode r1, TreeNode r2, TreeNode t){
        // left
        
        // 두 값이 서로 다른 경우 -> sum을 구함 && dfs를 타고 내려간다. 
        if(r1.left !=null && r2.left != null) {
            t.left = new TreeNode(r1.left.val+r2.left.val);
            dfs(r1.left,r2.left,t.left);
        }    
        if(r1.left == null) t.left = r2.left;
        if(r2.left == null) t.left = r1.left;
        
        // right 
        if(r1.right !=null && r2.right != null) {
            t.right = new TreeNode(r1.right.val+r2.right.val);
            dfs(r1.right,r2.right,t.right);
        }    
        if(r1.right == null) t.right = r2.right;
        if(r2.right == null) t.right = r1.right;    
    }
}

다른 풀이(python)

현재 내 방식은, 두 트리의 노드를 비교하고는, 매 번 아예 새로운 노드를 생성하는 방식이었다.

이전에 정렬된 두 List를 병합하는 문제에서는 하나의 List를 기준으로 두고 병합을 한 후에 남은 것을 덧붙이는 방식을 취하면서, 매 번 새로운 노드를 생성하는 부담은 없었음.

다른 사람의 풀이에서도, 하나의 트리를 기준으로 두고 푸는 방식이 있었음.

class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: TreeNode
        """
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        root1.val += root2.val
        
        root1.left = self.mergeTrees(root1.left,root2.left)
        root1.right = self.mergeTrees(root1.right,root2.right)
        
        return root1