Leetcode 236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点5 和节点1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2 输出：1
解题思路：
祖先的定义： 若节点 p在节点 root 的左（右）子树中，或 p=root，则称 root是 p的祖先。
最近公共祖先的定义： 设节点 root为节点 p,q的某公共祖先，若其左子节点 root.left和右子节点 root.right都不是 p,q的公共祖先，则称 root 是 “最近的公共祖先” 。
根据以上定义，若 root是 p,q的 最近公共祖先 ，则只可能为以下情况之一：
- p和 q在 root的子树中，且分列 root的 异侧（即分别在左、右子树中）；
- p=root ，且 q在 root 的左或右子树中；
- q=root，且 p在 root的左或右子树中；
考虑通过递归对二叉树进行先序遍历，当遇到节点 p 或 q时返回。从底至顶回溯，当节点 p,q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root。
终止条件：
当越过叶节点，则直接返回 null；
当 root等于 p,q，则直接返回 root ；
递推工作：
开启递归左子节点，返回值记为 left；
开启递归右子节点，返回值记为 right；
返回值： 根据 left和 right，可展开为四种情况；
当 left和 right同时为空 ：说明 root的左 / 右子树中都不包含 p,q，返回 null；
当 left和 right同时不为空 ：说明 p,q分列在 root的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root；
当 left为空 ，right不为空 ：p,q都不在 root的左子树中，直接返回 right。
具体可分为两种情况：
p,q其中一个在 root的 右子树 中，此时 right指向 p（假设为 p ）；
p,q两节点都在 root 的 右子树 中，此时的 right指向 最近公共祖先节点 ；
当 left 不为空 ， right为空 ：与情况 3. 同理；
代码实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q){
return root;
}
TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
if(leftNode == null && rightNode == null){
return null;
}else if (leftNode == null && rightNode!=null) {
return rightNode;
}else if (leftNode != null && rightNode==null) {
return leftNode;
}else {
return root;
}
}
}
代码跟踪：
假设我们有以下二叉树：
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
我们要找到节点 6 和节点 4 的最低共同祖先。
首先，我们从根节点 3 开始遍历。根据代码的逻辑，我们首先检查根节点是否为 null，或者是否与节点 6 或节点 4 相同。在这个例子中，根节点不是要查找的节点，所以我们继续在左子树上递归调用 lowestCommonAncestor 方法。
现在，我们进入节点 5。我们继续检查节点 5 是否为 null 或者与节点 6 或节点 4 相同，发现它也不是要查找的节点。所以，我们继续在节点 5 的左子树上递归调用 lowestCommonAncestor 方法。
我们进入节点 6，这是我们要查找的节点之一。根据代码的逻辑，我们返回节点 6 作为结果。
现在，我们回到节点 5，继续在右子树上递归调用 lowestCommonAncestor 方法。
我们进入节点 2，这不是我们要查找的节点。我们继续在节点 2 的左子树上递归调用 lowestCommonAncestor 方法。
我们进入节点 7，这也不是我们要查找的节点。我们继续在节点 7 的左子树上递归调用 lowestCommonAncestor 方法。
节点 7 的左子树为空，所以我们返回 null。
现在，我们回到节点 7，继续在右子树上递归调用 lowestCommonAncestor 方法。
节点 7 的右子树为空，所以我们返回 null。
现在，我们回到节点 2，继续检查节点 2 的右子树。
我们进入节点 4，这是我们要查找的节点之一。根据代码的逻辑，我们返回节点 4 作为结果。
现在，我们回到节点 5，我们已经在左子树和右子树中分别找到了节点 6 和节点 4。根据代码的逻辑，我们返回节点 5 作为结果。
最终，我们找到了节点 6 和节点 4 的最低共同祖先，它是节点 5。
总结：
- 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
- 在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
- 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。
可以说这里每一步，都是有难度的，都需要对二叉树，递归和回溯有一定的理解。
评论区