【LeetCode热题100】【二叉树】二叉树的最近公共祖先

叶茂林

发布于 2024-04-12 08:33:28

1110

发布于 2024-04-12 08:33:28

二叉树皆可递归，可以递归查找两个节点的所在地，如果两个节点一个在root的左子树一个在右子树，说明root就是公共祖先，并且因为是递归，root就是最近的，如果不是，往左右子树递归的时候返回来空的，那说明最近公共祖先在非空的一侧，如果root就是两个节点之一，那么就直接返回

class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (root == nullptr || root == p || root == q)
            return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (left == nullptr)
            return right;
        if (right == nullptr)
            return left;
        return root;
    }
};

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-11，如有侵权请联系 cloudcommunity@tencent.com 删除

leetcode