灵隐挂经

VO里的coding轮
合并两棵树，每个节点有一个key和value，每个节点下面有多个子节点，同一个parent下的子节点key是唯一的。要求合并后的树key相同的valu

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

3-20 11:56 +08:00):

面的Senior Mobile Eng.

两个树做bfs，key相同就加？

請問是什麼職位？App track?

感谢楼主分享。这题是不是默认两棵树的根节点有相同的key，然后bfs或者dfs都可以？否则没办法merge吧？

匿名用户 发表于 2025-3-23 14:18
感谢楼主分享。这题是不是默认两棵树的根节点有相同的key，然后bfs或者dfs都可以？否则没办法merge吧？

根节点默认key一样。DFS就行。BFS不知道可不可以，因为同一层不同parent的节点可能会有相同key的。
这题写出来最多也就是LC Med难度，但是N-ary树的题目做得实在太少了。

是n-ary tree合并的题吗？感觉跟doordash的menu tree有点像

没找到原题，自己写了一个版本大家参考一下

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

class NTree {
public:
    unordered_map<char, NTree*> children;
    char key;
    int val;
    NTree(char key, int val): key(key), val(val) {}
    ~NTree() {
        for (auto& child: children) {
            if (child.second) {
                delete child.second;
            }
        }
    }
   
    void print() {
        queue<NTree*> q;
        q.push(this);
        
        while (q.size()) {
            int size = q.size();
            for(; size > 0; --size) {
                auto cur = q.front();
                q.pop();
                cout << cur->key << ":" << cur->val << ",";
                for (auto pair: cur->children) {
                    q.push(pair.second);
                }
            } cout << endl;
        }
    }
};

class Solution {
public:
    NTree* merge(NTree* t1, NTree* t2) {
        if (!t1 || !t2) {
            return nullptr;
        }
        
        if (t1->key != t2->key) {
            return nullptr;
        }
        
        // 只有在t1,t2非空并且key相同时才能合并
        
        NTree* newTree = new NTree(t1->key, t1->val + t2->val);
        
        // 遍历t1->children，公共的节点merge，单独节点深度拷贝
        for (auto pair1: t1->children) {
            char key = pair1.first;
            NTree* child1 = pair1.second;
            if (t2->children.count(key)) {
                newTree->children[key] = merge(child1, t2->children[key]);
            } else {
                newTree->children[key] = deepCopy(child1);
            }
        }
        
        // 遍历t2->children，公共的节点已经merge，跳过，单独节点深度拷贝
        for (auto pair2: t2->children) {
            char key = pair2.first;
            NTree* child2 = pair2.second;
            if (!t1->children.count(key)) {
                newTree->children[key] = deepCopy(child2);
            }
        }
        
        return newTree;
    }
private:
    NTree* deepCopy(NTree* t) {
        if (!t) {
            return nullptr;
        }
        
        NTree* newTree = new NTree(t->key, t->val);
        for (auto& child: t->children) {
            newTree->children[child.first] = deepCopy(child.second);
        }
        
        return newTree;
    }
};

int main()
{
    std::cout<<"Built Tree1" << endl;
    NTree* t1 = new NTree('A', 3);
    t1->children['F'] = new NTree('F', 3);
    t1->children['B'] = new NTree('B', 1);
    t1->children['R'] = new NTree('R', 6);
    t1->print();
   
    std::cout<<"Built Tree2" << endl;
    NTree* t2 = new NTree('A', 8);
    t2->children['F'] = new NTree('F', 7);
    t2->children['R'] = new NTree('R', 3);
    t2->print();
   
    Solution s;
    std::cout<<"Merge Tree1 and Tree2" << endl;
    NTree* newTree = s.merge(t1, t2);
    newTree->print();

    return 0;
}


// print
Built Tree1
A:3,
R:6,B:1,F:3,
F:15,C:18,
Built Tree2
A:8,
R:3,F:7,
Merge Tree1 and Tree2
A:11,
F:10,B:1,R:9,
C:18,F:15,

截图更好阅读