🎈 原创

LCA：Lowest Common Ancestor

也就是在一棵二叉树中寻找给定的两个节点的最近公共节点

首先给定几个条件：

• (1) 结点中的数值域都是唯一的
• (2) p结点和q结点一定在树中
• (3) 非空结点与空结点的LCA是该非空结点

因此可以得出以下的结论：

• (1) 如果p是q的祖先，则p和q的LCA是p
• (2) 如果q是p的祖先，则q和p的LCA是q
• (3) 否则，假设p和q的LCA是t：
  • (a) p和q在t结点的不同子树中
  • (b) 整棵二叉树中只有t结点满足 p和q在该结点的不同子树中的

针对二叉树的性质，分成一般的二叉树和二叉查找树来分开讨论

普通二叉树

首先给出树结点的定义

struct BTNode {
    int val;
    BTNode *left, *right;
};

如果p或q有一者是另一个的祖先，那在遍历到该结点时即返回

否则，当p结点不是q结点的祖先，q也不是p结点的祖先，递归当前结点的左右子树

BTNode* LCA(BTNode* root, BTNode* p, BTNode* q) {
    if (!root)
        return nullptr;
    if (root == p  root == q)
        return root;

    BTNode *left = LCA(root->left, p, q), *right = LCA(root->right, p, q);

    if (!left && !right)
        return nullptr;

    if (!left)
        return right;
    if (!right)
        return left;

    return root; // 如果左右结点都不为空，说明当前结点为LCA
}

另一种更简洁的写法：

BTNode* LCA2(BTNode* root, BTNode* p, BTNode* q) {
    if (!root  root==p  root==q)
        return root;
    BTNode *left = LCA2(root->left, p, q), *right = LCA2(root->right, p, q);
    return !left? right: !right? left: root;
}

二叉查找树

普通二叉树因为没有规律，只能递归遍历左右子树。

而在二叉查找树中，可以利用左子树的值小于右子树的值这个特性，提供下一步遍历的方向。

也就是：

• (1) 如果p和q的数据都小于k结点的数据，那么t必然在k结点的左子树
• (2) 如果p和q的数据都大于k结点的数据，那么t必然在k结点的右子树
• (3) 如果k结点的数据在p结点和q结点的数据中间，那么p和q必然分居在结点的两棵子树中，则k就是LCA

BTNode* LCA_BST(BTNode* root, BTNode* p, BTNode* q) {
    if (!root)
        return nullptr;
    if (root == p  root == q)
        return root;
    if (p->val < root->val && q->val < root->val)
        return LCA_BST(root->left, p, q);
    if (p->val > root->val && q->val > root->val)
        return LCA_BST(root->right, p, q);

    return root;
}

另一种简洁的写法

BTNode* LCA_BST2(BTNode* root, BTNode* p, BTNode* q) {
    return (root->val - p->val) * (root->val - q->val) <= 0? root: LCA(p->val < root->val ? root->left: root->right, p, q);
}

Leetcode

一道 leetcode 上的 LCA 相关题目的实例供参考

题目链接

Solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root)
            return nullptr;

        if(root == p || root == q)
            return root;

        TreeNode* left = lca(root->left, p, q);
        TreeNode* right = lca(root->right, p, q);

        if(!left)
            return right;
        if(!right)
            return left;

        return root;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return lca(root, p, q);

    }
};