 |
1
starqoq Oct 17, 2019
你可以先比较节点，节点有三种修改情况，
不变（在修改前和修改后都出现），新增（在修改的时候新增），删除（类似）。 对于没有变化的节点，这个节点可能在修改中被换了位置，检查一下他的直接父节点是不是变化了 按照你具体的比较要求处理子树整体移动的情况。 对于没有变化也没有修改父节点，检查他的在兄弟中的顺序有没有变化。 |
 |
2
taogen Oct 17, 2019 via Android
同一顶点出发，两个图同时 BFS 放队列中，比较两个图的每一层的差集，存储所有差集的指针到 vector 中，高亮所有差集节点。
|
 |
3
tt67wq Oct 17, 2019
```
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); } ``` 这样行不行？ 我随手写的 |
 |
4
BiteTheDust Oct 17, 2019
可以同时在两边跑 dfs，这样可以跑出相同的部分 剩下的就都是不同的了
|
 |
5
ourleven OP @BiteTheDust 感谢！我去科普了下 dfs，收益匪浅。但是感觉没法套用这个场景啊！
举例，dfs 第一个树结果 a 到 b 到 c 到 e。dfs 第二个树结果，a 到 b 到 d 到 c 到 e。 结果我能得到 ab 相同，剩下的都不同。但 c 到 e 其实是相同的 |
|
9
BiteTheDust Oct 17, 2019
那你得准确地规定什么样算是相同 什么样算是不同了
如果仅仅是需要标记相同的父子关系 那只要枚举两个树每个节点，取他们孩子的交集就可以了 |
|
10
taogen Oct 17, 2019 via iPhone
初始状态：定义一个指针 levelPtr 表示指向每一层最后一个节点指针。让第一个节点根节点入队，level 指向根节点。
循环操作：队首元素出队，并把它所有子节点入队。判断当前出队节点是不是 levelptr 指向的，如果是则更换 levelptr 指向为最后一个入队的子节点，即为下一层的最后一个节点。 |
Select Language