狗家店面

limpalong 发表于 2018-9-3 01:44
这题好像是脸家的面筋题，找出两个node各自的深度，再找出他们lca的深度，然后各自深度相加-2*lca深度

昂为什么要这样做。直接从两个node网上找到lca，中途记录下走了多少步不就可以了吗

可以转换成graph 然后bfs吗？

感觉是 236. Lowest Common Ancestor of a Binary Tree

多谢分享

LZ的朋友来补充：题目不给root节点，node有parent属性

SaltSprayAir 发表于 2018-9-7 04:00
LZ的朋友来补充：题目不给root节点，node有parent属性

那就一路找回去，两边各一步，记录访问到的node，如果有重复，说明到lca了，再跑一遍计算步数就好了

请问找LCA的时候是用一个set记录其中一个节点的全部祖先(包括自己)，然后遍历另外一个节点的祖先(包括自己)，如果在set里面这个就是LCA?

byfwh 发表于 2018-10-12 06:16
请问找LCA的时候是用一个set记录其中一个节点的全部祖先(包括自己)，然后遍历另外一个节点的祖先(包括自己) ...

我觉得就是这样的

每日一题 发表于 2018-10-12 09:27
我觉得就是这样的

好的 谢谢 祝offer多多

谢谢楼主分享