LeetCode HOT100 - 二叉树的最近公共祖先

第一时间想的实际上是倍增，就是对于每个节点，记录它的 \(2^k\) 级祖先，查询 LCA 的时候让它们先跳到同一深度，接着再逐步向父节点移动

但是这样需要去预处理，并且这里是直接给出了函数和传进来的数据结构，所以换个角度考虑

怎么转换角度呢，如果考虑怎么去实现，那实际上还是一开始提到的思路

但是想到树的结构本身就是子结构或者同构问题，适合动态规划或者分治

这里我们要编写的函数的作用是在根为 root 的树中，找 p, q 的 LCA

考虑 p, q 可能的分布

• 一个在左子树，一个在右子树
• 两个都在左子树
• 两个都在右子树

对于第一种情况，显然 LCA 就是 root

对于第 2 、3 种情况，我们的结果等价于在根为 root 的左/右儿子 中，找 p, q 的 LCA

接着我们思考如何去刻画这一个关系，因为我们需要一个统一的策略，去处理 1，2，3

延续上面提到的思想，尝试把这个任务丢给左子树，右子树，也就是

        TreeNode *l = lowestCommonAncestor(root->left, p, q);
        TreeNode *r = lowestCommonAncestor(root->right, p, q);

如果是情况 2 ，那么 r 会是 nullptr ，返回 l ，反之亦然
如果是情况 1， 那么 l 和 r 都会是 nullptr，这时候返回 root

现在剩下递归边界情况

如果 root 已经是 nullptr ，自然返回 root；特殊一点的，如果 root 恰好是 p, q ，那么显然 LCA 是 root

/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q) {
            return root;
        }
        TreeNode *l = lowestCommonAncestor(root->left, p, q);
        TreeNode *r = lowestCommonAncestor(root->right, p, q);
        if(l == nullptr) {
            return r;
        }
        if(r == nullptr) {
            return l;
        }
        return root;
    }
};

另外在翻看别人的代码时发现 nullptr 或者说是否为空的判断可以写的更简单一些，也就是类似于判断是否为 0 的形式

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