algo-aha

bt两节点的最近公共祖先

• https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
	// 在子树中找p或q，找到一个就返回
	if (!root || root == p || root == q) return root;

	auto left = lowestCommonAncestor(root->left, p, q);
	auto right = lowestCommonAncestor(root->right, p, q);
	if (left && right) return root;  // p和q分别在左右子树，root就是lca
	return left ? left : right;      // p和q都在某个子树
}

bst两节点的最近公共祖先

• https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    // 找值在p、q间的节点
    if (!root || !p || !q) return NULL;
    if (p->val > q->val) swap(p, q); // p.val < q.val
    while (root) {
        if (root->val < p->val) {
            root = root->right;
        } else if (root->val > q->val) {
            root = root->left;
        } else {
            break;
        }
    }
    return root;
}

含所有最深叶节点的最近公共祖先

• https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
• https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

TreeNode* lcaDeepestLeaves(TreeNode* root) {
    return getHeight(root).second;
}

// 返回：(height, lcaWithDeepest)
pair<int, TreeNode*> getHeight(TreeNode *root) {
    if (!root) return {0, NULL};
    auto left = getHeight(root->left);
    auto right = getHeight(root->right);

    int h1 = left.first, h2 = right.first;
    if (h1 > h2) return {1 + h1, left.second};
    if (h1 < h2) return {1 + h2, right.second};
    return {1 + h1, root};
}