1740.Find-Distance-in-a-Binary-Tree

很显然，本题中的那个“拐点”必然是两个节点的LCA。

本题的解法可以很暴力，直接寻找从root到p与q分别的路径，根据记录路径然后找出LCA分别到p和q的长度。

更加节省空间的方法就是纯递归。在LC236的想法里，dfs(node)返回的是该节点的子树里包含了多少个p或者q。在本题中，我们可以有类似的思想：定义dfs(node)的返回值是一个pair，包含node与p的距离、node与q的距离。如果node下属没有子节点是p和q，那么对应的值是-1.

先分别递归ans1 = dfs(node->left, p, q)和ans2 = dfs(node->left, p, q). 分情况讨论：

1. 如果已知左节点到p的距离x，那么说明node到p的距离是x+1
2. 如果已知右节点到p的距离x，那么说明node到p的距离是x+1
3. 如果node本身就是p，那么说明node到p的距离是0
4. 其余的情况，node到p的距离标记为-1

同理，处理对于node到q的距离处理。

因为递归是从下往上走的，如果第一次出现node到p和q的距离都不是-1，那么node就是p和q的LCA。答案就是两距离之和。