LC 617 & LC 236

Solution to LeetCode 617 Merge Two Binary Trees, and LeetCode 236 Lowest Common Ancestor of a Binary Tree.

LeetCode 617

Merge Two Binary Trees (Easy) [link]

1] Recursive solution. Pre-order traversal. DFS.

# 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:
            return root2
        if not root2:
            return root1

        root1.val += root2.val # middle
        root1.left = self.mergeTrees(root1.left, root2.left) # left 
        root1.right = self.mergeTrees(root1.right, root2.right) # right
        return root1

2] Iterative solution.

# 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:
            return root2
        if not root2:
            return root1

        que = deque()
        que.append(root1)
        que.append(root2)
        while que:
            node1=que.popleft()
            node2=que.popleft()

            if node1.left and node2.left:
                que.append(node1.left)
                que.append(node2.left)

            if node1.right and node2.right:
                que.append(node1.right)
                que.append(node2.right)

            node1.val += node2.val
            if not node1.left and node2.left:
                node1.left = node2.left
            if not node1.right and node2.right:
                node1.right = node2.right

        return root1

LeetCode 236

Lowest Common Ancestor of a Binary Tree (Medium) [link]

The easiest way find the lowest common ancestor is going from bottom to top. Backtracking is the best way to do that.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        if left:
            return left
        return right