"""
Q617
Merge Two Binary Trees
Easy

Given two binary trees and 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 them 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 new tree.
"""

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

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1 or not t2:
            return t1 or t2

        # iterative
        # hard to change in place
        stack = [(t1, t2)]
        while stack:
            n1, n2 = stack.pop()
            if not n2:
                continue
            n1.val += n2.val
            if not n1.left:
                n1.left = n2.left
            else:
                stack.append((n1.left, n2.left))
            if not n1.right:
                n1.right = n2.right
            else:
                stack.append((n1.right, n2.right))

        return t1


a1 = TreeNode(1)
a2 = TreeNode(2)
a3 = TreeNode(3)

b1 = TreeNode(5)
b2 = TreeNode(5)
b3 = TreeNode(5)

a1.left = a2
a1.right = a3

b1.left = b2
b1.right = b3

sol = Solution()
tree = sol.mergeTrees(a1, b1)

def preorder(tree):
    if tree is not None:
        print(tree.val)
        preorder(tree.left)
        preorder(tree.right)

preorder(tree)





