LeetCode 236 二叉树的最近公共祖先(递归)

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

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

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 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。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

思路

乍一看是LCA的板子题，对于LCA问题，我们一般用 离线tarjan或者在线倍增来处理，或者用树链剖分

这几种算法，可以在我的ACM模板中找到最近公共祖先

但是这题只有一个查询，我们只需要用普通的递归来解决问题。

定义 $f_x$ 表示以 $x$ 为根的树中是否包含 $p$ 节点或者 $q$ 节点，则他们的最近公共祖先一定满足：

$$(f_{lson}&&f_{rson})||((x==p||x==q)&&({f_{lson}||f_{rson}})))$$

只要满足这个条件的点就是他们的公共祖先，那么能否保证这样找到的就是深度最小的祖先呢，dfs是自底向上的，所以最后一个满足条件的就是最近公共祖先。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
    TreeNode *ans;
    // root的子树中是否包含p或者q
    bool dfs(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        if (!root)
            return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || ((root->val == q->val || root->val == p->val) && (lson || rson)))
            ans = root;
        return lson || rson || root->val == p->val || root->val == q->val;
    }
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        dfs(root, p, q);
        return ans;
    }
};

最后修改于 2020-05-10

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。