（三十五）在二叉树中找到两个节点的最近公共祖先

【题目】给定一棵二叉树的头节点head，以及这棵二叉树中的两个节点O1、O2，请返回O1和O2的最近公共祖先。

【注意】

• 所有节点的值都是唯一的。
• O1、O2为不同节点且均存在于给定的二叉树中

【解题思路】

• 使用后序遍历，其回溯的过程就是从低向上遍历节点。
• 若找到一个节点，发现左子树出现结点O1，右子树出现节点O2，或者左子树出现结点O2，右子树出现节点O1，那么该节点就是节点O1和O2的最近公共祖先。
  • 如果当前节点cur等于NULL，或O1，O2则返回cur
  • 如果left和right都为空，说明cur上没有发现O1或O2，则返回NULL
  • 如果left和right都不为空，说明左子树上发现过O1或O2，右子树上发现过O2或O1。说明O1向上与O2向上的过程中首次在cur相遇，则返回cur；
  • 如果left和right有一个为空，另一个不为空，则记不为空的节点为node，node有两种可能：一种是node是O1、O2其中的一个，另一种则是node已经是O1、O2最近公共祖先。不管哪种情况，直接返回node即可。

【C++】

/*找到O1、O2的最近公共祖先*/
TreeNode* lowestAncestor(TreeNode* head,TreeNode* o1,TreeNode* o2){
	if(head == NULL || head == o1 || head == o2)
		return head;
	
	TreeNode* left = lowestAncestor(head->left,o1,o2);
	TreeNode* right = lowestAncestor(head->right,o1,o2);

	if(left != NULL && right != NULL)
		return head;
	
	return left != NULL ? left : right;
}

/*树的节点*/
struct TreeNode{
    int value;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int val){
        this->value = val;
        }
};