剑指offer(C++)-JZ86：在二叉树中找到两个节点的最近公共祖先(数据结构-树)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：树上节点数满足1≤n≤10^5  , 节点值val满足区间 [0,n)

要求：时间复杂度 O(n)

注：本题保证二叉树中每个节点的val值均不相同。

如当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：

所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3。

节点本身可以视为自己的祖先

输入：

{3,5,1,6,2,0,8,#,#,7,4},5,1

返回值：

3

本题考察数据结构树的使用，寻找最近公共祖先，用LCA算法解决。

1. 如果两个节点均在左子树内，则LCA(root,o1,o2)=LCA(root->left,o1,o2)；若其中一个节点正好是左子树根节点，则左子树根节点就是它俩的最近公共祖先。

2. 如果两个节点均在右子树内，则LCA(root,o1,o2)=LCA(root->right,o1,o2)；若其中一个节点正好是右子树根节点，则右子树根节点就是它俩的最近公共祖先。

3. 如果一个在左子树，一个在右子树，则当前的根节点就是最近公共祖先。

class Solution {
public:
    
    // LCA算法：寻找最近公共祖先
    TreeNode* LCA(TreeNode* root,int r1,int r2){
        // 节点为空
        if(!root)
            return NULL;
        // 是否寻找到目标值
        if(root->val == r1 || root->val == r2)
            return root;
        // 递归
        TreeNode* left=LCA(root->left,r1,r2);
        TreeNode* right=LCA(root->right,r1,r2);
        // 若左边有，右边没有，则目标在左边；若右边有，左边有，则目标在右边
        if(!left)
            return right;
        if(!right)
            return left;
        // 若左边和右边都有节点，则当前根为公共祖先
        return root;
    }
    
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        TreeNode* result=LCA(root,o1,o2);
        return result->val;
    }
};