公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 则节点 5 和节点 1 的最近公共祖先是节点 3 节点 5 和节点 4 的最近公共祖先是节点 5（因为根据定义最近公共祖先节点可以为节点本身）求解思路如下：
先判断给定的两个结点是否有一个为根结点，如果有一个结点为根结点，则直接返回根结点。否则判断两个结点是否在同一颗子树，如果不在，则它们最近的公共祖先结点也为根结点；如果同在左子树，重复上述过程；否则在右子树中重复上述过程。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ struct TreeNode* Find(struct TreeNode* root,int val) { if(root == NULL) { return NULL; } if(root->val == val) { return root; } struct TreeNode* found = Find(root->left,val); if(found != NULL) { return found; } return Find(root->right,val); } struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) { struct TreeNode* pInLeft = Find(root->left,p->val); struct TreeNode* qInLeft = Find(root->left,q->val); if(p == root || q == root) //判断给定结点是否是根结点 { return root; } if(pInLeft == NULL && qInLeft != NULL) //如果给定结点不 同在左子树，返回根结点 { return root; } if(pInLeft != NULL && qInLeft == NULL) //如果给定结点不 同在右子树，返回根结点 { return root; } if(pInLeft != NULL) //给定结点同在左子树 { return lowestCommonAncestor(root->left,p,q); } else //给定结点同在右子树 { return lowestCommonAncestor(root->right,p,q); } }
