230428/ leetcode / python/ 617. Merge Two Binary Trees, 116. Populating Next Right Pointers in Each Node

Problem 1

Merge Two Binary Trees - LeetCode

 

---

Solution1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1 or not root2:
            return root1 or root2
        
        new_node = TreeNode(val=root1.val + root2.val)

        
        def makeNewTree(root1, root2, cur_node):
            if not root1 or not root2:
                return
                        
            if not root1.left or not root2.left:
                cur_node.left = root1.left or root2.left
            else:
                cur_node.left = TreeNode(val=root1.left.val + root2.left.val)
            
            if not root1.right or not root2.right:
                cur_node.right = root1.right or root2.right
            else:
                cur_node.right = TreeNode(val=root1.right.val + root2.right.val)
                
            makeNewTree(root1.left, root2.left, cur_node.left)
            makeNewTree(root1.right, root2.right, cur_node.right)
        
        makeNewTree(root1, root2, new_node)
        
        return new_node

 

1. 일단 재귀는 써야겠다고 생각했음
2. 처음엔 root 자체를 한번에 돌릴 수 있을 거라고 생각했는데 left, right로 들어갈 때 각각 left, right 객체가 들어가야 햇음
3. 그래서 left랑 right를 따로 두번 돌려야겠다고 생각함

 

Refrerence

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1 and not root2:
            return 
        
        new_node = TreeNode(val=(root1.val if root1 else 0) + (root2.val if root2 else 0))
        new_node.left = self.mergeTrees(root1 and root1.left, root2 and root2.left)
        new_node.right = self.mergeTrees(root1 and root1.right, root2 and root2.right)
        
        return new_node

 

• 전체적인 흐름은 비슷한 것 같은데 구현이 많이 깔끔하다

 

Solution2 - Refactor

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1 or not root2:
            return root1 or root2
        
        new_node = TreeNode(val=root1.val + root2.val)
        
        def mergeNodes(node1, node2):
            if not node1 or not node2:
                return node1 or node2
            
            new_node = TreeNode(val=node1.val + node2.val)
            new_node.left = mergeNodes(node1.left, node2.left)
            new_node.right = mergeNodes(node1.right, node2.right)
            return new_node
        
        new_node.left = mergeNodes(root1.left, root2.left)
        new_node.right = mergeNodes(root1.right, root2.right)
        
        return new_node

 

• 시간복잡도 O(n)
• 코드는 조금 더 깔끔하게 쓰려는 노력은 해야겠다
• 아직 재귀 쓰는 게 조금 익숙하지 못해서 풀어서 쓰고 좀 돌아가는 경향이 있는데 앞으로 보완해나가야겠다

 

---

 

Problem2

Populating Next Right Pointers in Each Node - LeetCode

 

Solution1

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root
        
        queue = deque()
        queue.append(root)
        
        while queue:
            level = len(queue)
            for i in range(level):
                cur_node = queue.popleft()
                cur_node.next = None if i + 1 == level else queue[0]
                if cur_node.left:
                    queue.append(cur_node.left)
                if cur_node.right:
                    queue.append(cur_node.right)
        
        return root

 

• 전형적인 level order 문제로, bfs로 구현했음