leetcode-160
leetcode 236 二叉树的最近公共祖先
题目描述：二叉树的最近公共祖先
方法
递归
递归遍历整棵二叉树，定义 f(x) 表示 x 节点的子树中是否包含 p 节点或 q 节点，如果包含为 true，否则为 false。那么符合条件的最近公共祖先 x 一定满足如下条件：
1
(f(lson) && f(rson)) ∣∣ ((x = p ∣∣ x = q) && (f(lson) ∣∣ f(rson)))
其中
lson和rson分别代表 x 节点的左孩子和右孩子。上述条件比较复杂，分析以下就是：
f(lson) && f(rson):
表示节点 x 的左子树中包含p节点或者q节点，同时x的右子树中也包含p节点或者q节点。因为是 && 的关系，所以一定是左右分别有p或q中的一个。此时x一定是p和q的最近公共祖先
(x = p ∣∣ x = q) && (f(lson) ∣∣ f(rson)):
这个布尔表达式很直观：节点x是p或者q中的一个，同时x
的左右子树中包含p或者q中的另一个。
存储父节点
题解代码
递归
1 |
存储父节点
1 |