面试官的问题：写一个函数 TreeNode* Find(TreeNode* root, TreeNode* p, TreeNode* q) ，返回二叉树中p和q的最近公共父节点。
本人反应：当时有点紧张，没怎么想就直接上手敲代码，一边想一边敲代码，越敲越想不出来，越想不出来越尴尬、越紧张...
鼓捣了十几分钟都没个头绪，面试官随意提示了两句，我感觉压力更大了... 就随便想了个思路就乱写（思维拐进了死胡同，弯路越走越远.......）
最后思路太跑偏了，就说了下当时脑子里很偏的思路，结果果然gg....
面试总共半小时左右就结束了： 开头的自我介绍就随便说了五分钟左右，没几句话就问了这个问题，结果思路跑偏，敲代码前前后后就二十多分钟，后面直接就“面试结束，你还有什么问题吗？”.... 我问了下工作相关的方向和地点，然后就彻底结束了....
下来自己仔细想了想，从递归的意义和原理入手，马上就有了思路... （哎，台上半小时都想不到，台下两分钟就有雏形了。还是得多面试面试，增强心理素质和脸皮厚度.......）
话不多说，直接上答案：
#define _CRT_SECURE_NO_WARNINGS //VS用scanf会报错，加了这个就ok了
#include<cstdio>
//360一面，二叉树中两节点的最近公共父节点
struct TreeNode{
int val;
TreeNode *left, *right;
TreeNode(int x = ) :val(x) { left = right = ; }
}*root; //为了测试方便，把p和q的类型改成int（面试现场可以不用改，直接敲完并描述思路就好吧）
//不然得直接比较两个指针的地址，先要取到二叉树中两个节点的地址太麻烦
TreeNode* Find(TreeNode* root, int p, int q) {
//递归先确定返回条件和返回值。
if (root == )return ; //没找到就一直到最底层，返回0
if (root->val == p || root->val == q)return root; //找到了就先返回自己，非0值 //其次应该根据递归的意义想到成功和失败的条件，及返回值
//先找左子树和右子树，下面的代码应该从底向上思考
TreeNode* a = Find(root->left, p, q);
TreeNode* b = Find(root->right, p, q);
//从底向上思考，先在底层执行，后在上层执行。
//当左边和右边各有一个时，显然成功，当前节点就是所求结果
if (a&&b)return root;
//当只有左边有一个时，答案在上层，先往上返回非0值
if (a)return a;
//当只有右边有一个时，答案在上层，先往上返回非0值
if (b)return b;
//左右都没有时，就返回0值
return ;
} //构建有tot-now+1个节点的树，从上到下、从左到右的编号为从now到tot
TreeNode* build(int now, int tot) {
if (now > tot)return ;
TreeNode* root = new TreeNode(now);
root->left = build(now * , tot);
root->right = build(now * + , tot);
return root;
} //delete掉new的全部内存空间
void deleteAll(TreeNode* root) {
if (root == )return;
deleteAll(root->left);
deleteAll(root->right);
delete root;
} int main() {
root = build(, );//构建4层的满二叉树
int a[][] = { {,},{,},{,},{,} };//4个测试样例
TreeNode* fa;
for (int i = ; i < ; i++) {
fa = Find(root, a[i][], a[i][]);
if (fa)printf("Common parent of (%d,%d) is %d\n", a[i][], a[i][], fa->val);
else printf("Common parent of (%d,%d) is NULL\n", a[i][], a[i][]);
} deleteAll(root);
return ;
}
证明算法的正确性：
构造了一个这样的二叉树： 1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
1. 若p，q有一个是1（root节点），则会直接返回root，显然正确。
2. p，q的直接父节点相同时，p会返回非0，q会返回非0，所以直接父节点会返回本身，再上层会返回答案节点。 其他路径会搜索到最底层并返回0。
3. p，q的直接父节点不同时，p返回非0，上层都会返回非0；q会返回非0，上层都会返回非0。直到最近公共父节点会返回自己，再上层会返回答案节点。其他路径会搜索到最底层并返回0。
此算法没有使用二叉树中节点之间的任何关系，直接递归遍历整棵树，以值（或地址）相等为返回条件，通用性非常强。
用在节点间有特殊关系的情况下，还可以利用节点间的关系（大小等）进行剪枝，使其他路径无需搜索到最底层就提前返回。