最近公共祖先 (LCA)

1. 朴素法：普通递归

这是最直观的方法。从根节点开始递归，对于每个节点，检查是否是p或q，或者p和q是否在它的两侧子树中。如果是，那么这个节点就是LCA。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 实现寻找最近公共祖先的函数
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);
    
    // 如果p和q分别在root的两侧，那么root就是它们的最近公共祖先
    if (left && right) return root;
    
    // 否则，p和q都在一侧子树中，返回该子树的递归结果
    return left ? left : right;
}

int lca(int root, int a, int b) {
	if (!root)
		return -1;

	if (root == a || root == b) 
		return root;

	int l = lca(lch[root], a, b);
	int r = lca(rch[root], a, b);

	if (l != -1 && r != -1)
		return root;
	if (r != -1)
		return r;
	if (l != -1)
		return l;
	return -1;
}