【经典算法题】二叉树的最近公共祖先

【经典算法题】二叉树的最近公共祖先,第1张

【经典算法题】二叉树的最近公共祖先 【经典算法题】二叉树的最近公共祖先 Leetcode 0235 二叉搜索树的最近公共祖先

题目描述:Leetcode 0235 二叉搜索树的最近公共祖先

分析

  • 本题的考点:LCA(最近公共祖先)

  • 关于LCA问题可以参考:网址。

  • 因为是二叉搜索树,所以我们可以根据值的大小递归求解。如果两个节点的值都小于根节点的值,则进入左子树搜索;否则若两个节点的值都大于根节点的值,则进入右子树搜索;否则当前根节点就是LCA。

代码

  • C++
class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    
        if (!root) return NULL;
        if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
        if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
        return root;
    }
};

  • Java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        if (root == null) return null;
        if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
        if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

时空复杂度分析

  • 时间复杂度: O ( h ) O(h) O(h),h为树高。

  • 空间复杂度: O ( h ) O(h) O(h)。

Leetcode 0236 二叉树的最近公共祖先

题目描述:Leetcode 0236 二叉树的最近公共祖先

分析

  • 本题的考点:LCA

  • 关于LCA问题可以参考:网址。

  • 后续递归遍历两棵子树,第一次发现某棵子树中既有p又有q,则该子树的根节点为p和q的最近公共祖先。如下图:

代码

  • C++
// 写法一
class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {

        if (!root || root == p || root == q) return root;
        auto l = lowestCommonAncestor(root->left, p, q), r = lowestCommonAncestor(root->right, p, q);
        if (l && r) return root;  // 第一次左右非空, 此时对应的root是LCA
        if (l) return l;
        return r;  // right也可能为空节点
    }
};
// 写法二
class Solution {
public:
    TreeNode* ans = NULL;

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {

        dfs(root, p, q);
        return ans;
    }

    // 返回值是一个二进制的数,最低位是1的话表示该棵子树存在p,从右向左第二位是1的话表示该棵子树存在q。
    int dfs(TreeNode *root, TreeNode *p, TreeNode *q) {

        if (!root) return 0;

        int state = 0;
        if (root == p) state |= 1;
        else if (root == q) state |= 2;
        
        state |= dfs(root->left, p, q);
        state |= dfs(root->right, p, q);

        if (state == 3 && !ans) ans = root;  // 只有第一次找到的才是LCA
        return state;
    }
};
  • Java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q), right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;  // 第一次左右非空, 此时对应的root是LCA
        if (left != null) return left;
        return right;  // right也肯能为空节点
    }
}

时空复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),n为树中节点数。

  • 空间复杂度: O ( h ) O(h) O(h),h为树高。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5610356.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-15
下一篇 2022-12-15

发表评论

登录后才能评论

评论列表(0条)

保存