Leetcode hot100 二叉树的最近公共祖先【中等】

太久没做递归了，用分治法想了一个很蠢的方式，分成了好几步。

1. 遍历以p为根节点的树看是否有q，有的话，返回p
2. 遍历以q为根节点的树看是否有p，有的话，返回q
3. 到了这里，说明p和q是“分开的”。
   1. 以root为根节点，遍历左子树，看是
      1. “p和q都有”：那就是p和q都在左子树里，计算p和q的深度，取二者深度最小值，减去1，这个位置对应的节点就是最近的公共祖先
      2. “只有p或只有q”：那root就是最近的公共祖先，返回root
      3. “p和q都没有”：那就是p和q都在右子树里。。。

太智障了。。亏我想得出来。。

法（一）

这个题难在递推问题的定义上，dfs(ListNode root,ListNode p,ListNode q)不是定义为“以root为根节点的树中，p和q的最近公共祖先”，而是定义为“以root为根节点的树，是否有p或者q”

注意不要用下面这种写法，递归问题的定义非常混乱

还是采用官方给出的递归子问题定义更清晰

返回值是boolean。