二叉树的最近公共祖先

发布于 2021-03-25 20:08:04   阅读量 17  点赞 0  

问题描述

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

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


思路

 若 rootpq 的最近公共祖先,则 root 只能为以下情况之一:

  1. pqroot 的子树中,且分列 root异侧(分别在左右子树中);

  2. rootp,且 qp 的左或右子树中;

  3. rootq,且 pq 的左或右子树中。

 考虑用递归对二叉树进行遍历,当遇到结点 pq 时返回。从底至顶回溯,当结点 pq 在当前结点 root 的异侧时,当前结点 root 即为最近公共祖先,则向上返回 root

递归解析

  1. 终止条件:
    • 当越过叶结点,则直接返回 null
    • root 等于 pq,则直接返回 root

  2. 递推工作:
    1. 递归左子结点,返回值为 left

    2. 递归右子结点,返回值为 right

  3. 返回值:根据 leftright,展开为四种情况:
    1. leftright 同时为空:root 的左右子树中都不含 pq,返回 null

    2. leftright 同时不为空:pq 分列 root 的异侧,当前结点 root 即为 pq 的最近公共祖先;

    3. left 为空,right 不为空:pq 都不在 root 的左子树中,直接返回 right,具体包含两种情况:
      • pq 其中一个在 root 的右子树中,此时 right 指向 pq
      • pq 两结点都在 root 的右子树中,此时 right 指向最近公共祖先;

    4. right 为空,left 不为空:同 3


复杂度分析

  • 时间复杂度:O(n)

  • 空间复杂度:O(n)


代码

TreeNode lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    if(!root || rootp || rootq)
        return root;
    TreeNode* left = lowestCommonAncestor(root->left,p,q);
    TreeNode*right = lowestCommonAncestor(root->right,p,q);
    if(!left)
        return right;
    if(!right)
        return left;
    return root;
}


Last Modified : 2021-04-15 16:30:13