一、题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

二、代码思路

K神的详细题解

比较重要的三点：

最近公共祖先节点的定义：

1. root作为最近祖先节点，p 和 q应该分列两侧，并且root.left 与 root.right 不是 p q的祖先
2. q作为root，p在其左或右子树中
3. p作为root，q在其左或右子树中

结合PPT看题解就知道为啥这么写了

1. 有点类似于后序遍历，通过判断某个根节点的子节点是否含有p q，来确定递归的返回值。
2. 一旦找到p 或 q就退出当前递归层，然后开始从底部向上层层回溯。

看代码和PPT更好理解

三、代码题解

package leetcode.lc20221216;/** @author lzy* @version 1.0* */
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}
public class Solution01 {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//最近公共祖先节点的定义：//1. root作为最近祖先节点，p 和 q应该分列两侧，并且root.left 与 root.right子树中//2. q作为root，p在其左或右子树中//3. p作为root，q在其左或右子树中//当root为p或q时应该即刻返回，因为如果再往下遍历，不可能找到两者祖先，因为p已经遍历过了//对应于2 3 情况if (root == null || root == p || root == q) {return root;}//类似与中序遍历序列，以下是判断第一种情况的TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);//左右子树中都没有if (left == null && right == null) {return null;}// 左子树没找到if (left == null) {return right;}//右子树没找到if (right == null) {return left;}//左右子树都找到了return root;}
}