XingHuiSamaの宝藏之地

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

百度百科中最近公共祖先的定义为：“对于有根树 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

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

‍
‍

1. 算法核心思路

求解二叉树中两个节点的最近公共祖先（LCA），一种直观且易于理解的思路是路径比对法。该算法的核心逻辑分为两步：

记录路径：利用深度优先搜索（DFS），分别找出从根节点到达目标节点 p 和 q 的完整路径，并将其存储在两个数组中。
寻找分叉点：由于两条路径均从根节点出发，它们必然拥有一段相同的“前缀”。从头开始逐项对比这两个路径数组，最后一个相同的节点，即为这两个节点的最近公共祖先。

2. 算法步骤拆解

DFS 搜索与回溯：为了记录路径，可以设计一个递归函数 func(list, node, tar)。在遍历过程中，先将当前节点推入数组 list。若当前节点即为目标节点，则停止当前搜索分支并返回；若不是，则依次向左右子树继续搜索。若左右子树均未找到目标节点，说明当前节点不在通往目标的路径上，需要将其从数组中弹出（即回溯）。在此过程中，引入一个全局或成员变量 flag 来标识是否已经找到目标节点，用于剪枝，避免不必要的全树遍历。
路径对比与防越界：获取到 list1 和 list2 后，需对比找出最后一个相同的节点。为了防止数组越界，对比的循环上限必须取两个数组长度的最小值（min(list1.size(), list2.size())）。在循环中，一旦遇到第一个不相同的节点，其前一个节点即为所求的公共祖先。若循环完整结束，说明其中一条路径是另一条路径的完全前缀，此时较短路径的最后一个节点即为公共祖先。

‍
‍

class Solution {
public:
    int flag = 1; // 用于控制 DFS 搜索状态的标志位
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> list1, list2;
        
        // 寻找通往节点 p 的路径，搜索前重置标志位
        flag = 1;
        func(list1, root, p);
        
        // 寻找通往节点 q 的路径，搜索前重置标志位
        flag = 1;
        func(list2, root, q);

        // 取两个路径长度的最小值，防止后续遍历越界
        int len = min(list1.size(), list2.size());

        // 对比两条路径，寻找分叉点
        for (int i = 0; i < len; i++) {
            if (list1[i] != list2[i]) {
                return list1[i - 1]; // 遇到分叉，返回上一个相同的节点
            }
        }

        // 若其中一条路径完全是另一条的前缀，则返回较短路径的末尾节点
        return list1[len - 1];
    }
    
    void func(vector<TreeNode*> &list, TreeNode* node, TreeNode* tar) {
        if (node == NULL) {
            return;
        }

        // 记录当前节点
        list.push_back(node);

        // 找到目标节点，修改标志位并终止当前搜索分支
        if (node == tar) {
            flag = 0;
            return;
        }

        // 若尚未找到目标，继续搜索左子树
        if (flag == 1) {
            func(list, node->left, tar);
        }

        // 若尚未找到目标，继续搜索右子树
        if (flag == 1) {
            func(list, node->right, tar);
        }

        // 左右子树均搜索完毕且未找到目标，进行状态回溯
        if (flag == 1) {
            list.pop_back();
        }
    }
};

3. 复杂度分析

时间复杂度：**** $O(N)$

其中 $N$ 为二叉树的节点总数。最坏情况下（例如树退化为链表且目标节点位于叶子节点），需要完整遍历两遍二叉树来获取两条路径，时间开销与节点总数呈线性关系。后续的路径对比过程，时间开销不超过 $O(N)$ 。因此总体时间复杂度为 $O(N)$ 。
空间复杂度：**** $O(N)$

主要空间开销来自于递归调用栈的最大深度以及用于记录路径的数组 list1 和 list2。在最坏情况下，树的深度可达 $N$ ，此时数组的长度及递归栈深度均为 $N$ 。因此总体空间复杂度为 $O(N)$ 。

‍