万能的 V2，求问两颗树林的比较差异问题

[ourleven]

我手头有张森林的图，一个节点很多孩子，到另 n 个节点，保存为数据 a。现在别人编辑修改后，保存为数据 b。

现在问题是，如何高亮显示 a 和 b 的差异部分？有个算法吗？

每个节点或者方向线都有唯一标识。我的想法是遍历 a 的每个节点和方向线，看 b 里存不存在，不存在的都标记更改。最后 b 里剩下的是多出来的。也不知对不对？

没学过图论，非程序员科班出身，求大大们指点一二。

[starqoq]

你可以先比较节点，节点有三种修改情况，
不变（在修改前和修改后都出现），新增（在修改的时候新增），删除（类似）。

对于没有变化的节点，这个节点可能在修改中被换了位置，检查一下他的直接父节点是不是变化了
按照你具体的比较要求处理子树整体移动的情况。

对于没有变化也没有修改父节点，检查他的在兄弟中的顺序有没有变化。

[taogen]

同一顶点出发，两个图同时 BFS 放队列中，比较两个图的每一层的差集，存储所有差集的指针到 vector 中，高亮所有差集节点。

[tt67wq]

```
bool cmpTree(struct TreeNode *node1, struct TreeNode *node2) {
if (node1 == NULL && node2 == NULL)
return true;

if (node1 == NULL && node2 != NULL)
return false;

if (node1 != NULL && node2 == NULL)
return false;

if (node1->val != node2->val)
// 按楼主的意思，这里给改个颜色
return false;

return cmpTree(node1->left, node2->left) &&
cmpTree(node1->right, node2->right);
}

```
这样行不行？ 我随手写的

[BiteTheDust]

可以同时在两边跑 dfs，这样可以跑出相同的部分 剩下的就都是不同的了

[ourleven]

@BiteTheDust 感谢！我去科普了下 dfs，收益匪浅。但是感觉没法套用这个场景啊！
举例，dfs 第一个树结果 a 到 b 到 c 到 e。dfs 第二个树结果，a 到 b 到 d 到 c 到 e。

结果我能得到 ab 相同，剩下的都不同。但 c 到 e 其实是相同的

[ourleven]

@tt67wq 感谢！
好像简单了点？这样应该是有漏的。到后面不相同了就停了。然而是想要所有的不同

[ourleven]

@taogen 谢谢！
但问题是。。。怎么区分每一层呢？

[ourleven]

@starqoq 多谢！目前看起来倾向于这么比对了😂😂

[BiteTheDust]

那你得准确地规定什么样算是相同 什么样算是不同了
如果仅仅是需要标记相同的父子关系 那只要枚举两个树每个节点，取他们孩子的交集就可以了

[taogen]

初始状态：定义一个指针 levelPtr 表示指向每一层最后一个节点指针。让第一个节点根节点入队，level 指向根节点。
循环操作：队首元素出队，并把它所有子节点入队。判断当前出队节点是不是 levelptr 指向的，如果是则更换 levelptr 指向为最后一个入队的子节点，即为下一层的最后一个节点。