问题描述

  1. 给定一颗二叉树，找到该树种两个指定节点p和q的最近公共祖先
  2. https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

我的思路

  1. 从root开始，一次判断每个节点是否同时包含节点p，q，重点是同时包含，一直到根节点同时包含p,q但是左孩子和右孩子都不同时包含p，q时为止！
  2. 思路的缺点：
    • 因为是判断是否同时包含，所以必须设两个flag，一直等到dfs进行完之后才能看出是否同时包含！
    • 需要进行n次dfs，效率低下。

最优思路

  1. 进行dfs，判断是否包含p或q，再按照一下两个条件之一来判断x是否为最近公共祖先！
    • (lson&&rson)：x的左孩子和右孩子同时满足“包含p或q”这个条件，所以一定是左孩子中包含一个，右孩子种包含另外一个，所以x一定是最近公共祖先。
    • ((x.val==p.val||x.val==q.val)||(lson||rson))：x为p或q之一，此时只需其左孩子或右孩子包含另外一个节点即可！
  2. 上述思路优点
    • 只需一次dfs即可
    • 同时利用了dfs的返回值，以及在dfs过程种对一个全局变量进行设两个作用！