每日一题——在二叉树中找到两个节点的最近公共祖先

每日一题——在二叉树中找到两个节点的最近公共祖先

引用

CSDN

1.

https://m.blog.csdn.net/zxjiaya/article/details/145399481

在二叉树中寻找两个节点的最近公共祖先是一个经典的算法问题。本文将从题目描述、解题思路到代码实现，详细讲解如何解决这个问题。

题目描述

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

数据范围

• 树上节点数满足 $1 \leq n \leq 10^5$。
• 节点值 val 满足区间 [0, n)。
• 本题保证二叉树中每个节点的 val 值均不相同。

输入输出

输入：

• 输入树的节点，格式为一个数组表示二叉树的层序遍历，# 表示空节点。
• 输入两个整数 o1 和 o2，表示需要查找最近公共祖先的两个节点的值。

输出：

• 输出节点值，即 o1 和 o2 的最近公共祖先的值。

示例

示例 1：

输入：

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

输出：

3

示例 2：

输入：

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

输出：

2

解题思路

要解决这个问题，我们可以使用递归的方法遍历二叉树。具体的思路如下：

1. 递归终止条件：

• 如果当前节点为空，返回 NULL（表示未找到 o1 和 o2）。
• 如果当前节点的值是 o1 或 o2，说明找到了其中一个节点，返回当前节点。

2. 递归查找左子树和右子树：

• 分别在左子树和右子树中查找 o1 和 o2。
• 如果左子树找到一个节点，右子树也找到一个节点，说明当前节点是最近公共祖先，返回当前节点的值。
• 如果只有左子树或右子树找到节点，则递归返回找到的节点。

3. 时间复杂度：

• 每个节点最多遍历一次，因此时间复杂度为 $O(n)$，其中 $n$ 为二叉树的节点数。

C代码实现

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 查找最近公共祖先的函数
int lowestCommonAncestor(struct TreeNode* root, int o1, int o2) {
    if (root == NULL) {
        return -1; // 如果当前节点为空，返回-1
    }
    
    // 如果当前节点是o1或o2，返回当前节点
    if (root->val == o1 || root->val == o2) {
        return root->val;
    }
    // 在左子树和右子树中递归查找o1和o2
    int left = lowestCommonAncestor(root->left, o1, o2);
    int right = lowestCommonAncestor(root->right, o1, o2);
    // 如果在左子树和右子树中分别找到了o1和o2，当前节点就是最近公共祖先
    if (left != -1 && right != -1) {
        return root->val;
    }
    // 如果只在左子树或右子树中找到o1或o2，返回找到的那个节点
    return (left != -1) ? left : right;
}

代码解释

1. 节点定义：

• 我们首先定义了二叉树的节点结构体 TreeNode，它包含了三个成员：
• val：节点的值。
• left：指向左子树的指针。
• right：指向右子树的指针。

2. 递归函数：

• lowestCommonAncestor 函数通过递归查找左右子树，判断每个子树中是否包含 o1 和 o2，并最终找到最近公共祖先。
• 基本的递归步骤是：
• 如果当前节点为空，返回 -1。
• 如果当前节点的值是 o1 或 o2，则返回该节点的值。
• 否则递归查找左子树和右子树，合并结果。

3. 最终返回值：

• 如果左子树和右子树都找到了目标节点，则当前节点是最近公共祖先，返回当前节点的值。
• 如果只有左子树或右子树找到了目标节点，则返回找到的那个子树的值。

总结

最开始还觉得这题确实挺难的，但是其实只要仔细思考这题，难度其实也并不大。一层一层的递归找到。这个根节点。然后再一层层的返回。返回的节点，肯定都是他的祖宗结点。当满足左子树。和右子树各有一个时候，就可以返回当前结点。如果都在一侧，说明当前节点就是最近祖先节点。通过递归的方式，我们可以高效地解决二叉树中两个节点的最近公共祖先问题。该方法的时间复杂度为 $O(n)$，空间复杂度为 $O(h)$，其中 $h$ 是二叉树的高度。