Submission

Score: 100

User: mantaggez

Problemset: composite tree

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-22 12:43:04

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int val) {
        data = val;
        left = NULL;
        right = NULL;
    }
};

string tree1, tree2, ans;
Node *root1, *root2;

void preorder(Node *u)
{
    if(u == NULL) return ;
    cout << u -> data << ' ';
    preorder(u -> left);
    preorder(u -> right);
}

void build(string s, Node* &root)
{
    if(s.empty()) return ;

    string l = "", r = "";
    int b = 0, ropen = 0, cnt = 0, f = 0;
    for(char& c : s) {
        // if(ropen == 0) cnt++;
        // if(cnt == 2 && f == 0) f = 1;
        if('1' <= c && c <= '9' && ropen == 1) {
            f++;
            if(b > 1) f = 2;
        }
        if(c == '(') ropen++, b++;
        else if(c == ')') ropen--, b++;
        
        if(f == 1 && ropen != 0) {
            l += c;
        }
        if(f == 2 && ropen != 0) {
            r += c;
        }
    }

    int val = s[0] - '0';
    // cout << val << '\n';
    // cout << s << '\n';

    root = new Node(val);
    build(l.substr(0, l.size() - 1), root -> left);
    build(r, root -> right);
}

string answer(Node* &root1, Node* &root2)
{
    if(root1 == NULL || root2 == NULL) return "";

    string s = "";
    int val = (root1 -> data) + (root2 -> data);
    // cout << root1 -> data << ' ' << root2 -> data << '\n';
    string cv = to_string(val);
    s += cv + "(" + answer(root1 -> left, root2 -> left) + ")" + "(" + answer(root1 -> right, root2 -> right) + ")";
    return s;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> tree1 >> tree2;
    build(tree1, root1);
    build(tree2, root2);

    // cout << "Tree1 : ";
    // preorder(root1);
    // cout << '\n';

    // cout << "Tree2 : ";
    // preorder(root2);
    // cout << '\n';

    cout << answer(root1, root2) << '\n';

    return 0;
}

/*
5(2(8()())())(1(6(2()())(3()()))())
3(4()())(8(1(2()())())(3()()))
*/