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

太久没做递归了用分治法想了一个很蠢的方式分成了好几步。遍历以p为根节点的树看是否有q有的话返回p遍历以q为根节点的树看是否有p有的话返回q到了这里说明p和q是“分开的”。以root为根节点遍历左子树看是“p和q都有”那就是p和q都在左子树里计算p和q的深度取二者深度最小值减去1这个位置对应的节点就是最近的公共祖先“只有p或只有q”那root就是最近的公共祖先返回root“p和q都没有”那就是p和q都在右子树里。。。太智障了。。亏我想得出来。。法一这个题难在递推问题的定义上dfs(ListNode root,ListNode p,ListNode q)不是定义为“以root为根节点的树中p和q的最近公共祖先”而是定义为“以root为根节点的树是否有p或者q”注意不要用下面这种写法递归问题的定义非常混乱还是采用官方给出的递归子问题定义更清晰返回值是boolean。