给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：对这棵树 t 左右子树分别向下遍历，如果一个结点反馈回来的信息表明分别在左右子树中，则返回这个结点。如果只有一个结点返回，那这个结点就是最近公共祖先。

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root == NULL) return root; //树空返回root
    if(root == p || root == q) return root; //找到p和q返回root
    TreeNode* lNode = lowestCommonAncestor(root->left,p,q);
    TreeNode* rNode = lowestCommonAncestor(root->right,p,q);
    if(lNode != NULL && rNode != NULL) return root; //p，q分别在左右子树
    else if(lNode == NULL) return rNode; //左边没有
    else return lNode; //右边没有
}

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：对这棵树，将 p 、q 的值与根 root 做比较，如果 p ->val、q->val 都比 root->val 小，则递归去往左子树，如果都比 root->val 大，递归去往右子树，如果一个比 root->val 大，一个比 root->val 小，返回root。

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root == p || root == q) return root; //找到p或q
    if(p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left,p,q); //遍历左子树
    else if(p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right,p,q); //遍历右子树
    else return root; //找到公共祖先
}