本文共 1630 字，大约阅读时间需要 5 分钟。

寻找二叉树中两个节点的最低公共祖先（LCA）

在二叉树结构中，寻找两个给定节点的最低公共祖先（Lowest Common Ancestor，简称LCA）是一个常见的问题。LCA被定义为共有两个目标节点的最低层的公共祖先节点，包括这两个节点各自的路径。这意味着这个节点是两个目标节点上excluding彼此的共同祖先。

问题描述

给定如下二叉树结构：

3     /     \    5      1   / \   / \  6   2  0   8 /  \4    7

示例1：LCA(5, 1) 为节点3。此外，根据LCA的定义，一个节点可以是自己的祖先（此处的特殊情况，但实际应用中需明确节点是否为真实存在的条件）。

示例2：LCA(5,4) 为节点5，这是因为根据LCA的定义，节点可以是自己的子节点。

方法思路

要找出两个节点的最低公共祖先，我们可以采用以下方法：

具体实现

我们采用类似递归的方式来实现这个过程：

代码解析

class Solution {    vector
   
     path1;    vector
    
      path2;    bool dfs(TreeNode* root, TreeNode* target, vector
     
      & path) {        path.push_back(root);        if (root == target) return true;        if (dfs(root->left, target, path)) return true;        if (dfs(root->right, target, path)) return true;        path.pop_back();        return false;    }    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        path1.clear();        path2.clear();        if (!dfs(root, p, path1) || !dfs(root, q, path2)) return NULL;        int pos = 0;        int len = min(path1.size(), path2.size());        TreeNode* common = NULL;        while (pos < len && path1[pos] == path2[pos]) {            common = path1[pos++];        }        return common;    }};
     
    
   

思路总结

这种方法确保我们能在有限时间内找到两个节点的最低公共祖先，适用于所有二叉树结构。