Python sol o(n)


#1
def solve(self, A, B):
    def recsum(A,B,C):
        valA=0
        valB=0
        Aright=None
        Aleft=None
        Bright=None
        Bleft=None
        if A:
            valA=A.val
            Aright=A.right
            Aleft=A.left
        if B:
            valB=B.val
            Bright=B.right
            Bleft=B.left
        if A or B:
            C.val=valA+valB
        if Aleft or Bleft:
            Cnewl=TreeNode(0)
            C.left=Cnewl
            recsum(Aleft,Bleft,Cnewl)
        if Aright or Bright:
            Cnewr=TreeNode(0)
            C.right=Cnewr
            recsum(Aright,Bright,Cnewr)
    ret = TreeNode(0)
    recsum(A,B,ret)
    return ret