二叉树最近公共祖先（后序遍历，回溯算法）

236. 二叉树的最近公共祖先 - 力扣（LeetCode） 

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==p||root==q||root==NULL){return root;}TreeNode*left=lowestCommonAncestor(root->left,p,q);TreeNode*right=lowestCommonAncestor(root->right,p,q);if(left==NULL&&right!=NULL){return right;}else if(left!=NULL&&right==NULL){return left;}else if(left==NULL&&right==NULL){return NULL;}else{return root;}}
};

要想找二叉树的最近公共祖先，要从叶子节点开始遍历，最后返回给根节点，所以采用后序遍历的方法实现。

判断符合题意条件：在遍历到的节点时，此节点与目标节点相同时，则返回节点给根节点，如果为空，则返回空。

单层递归逻辑：递归遍历节点的左右子节点，储存在left和right中。

回溯逻辑：如果节点的左节点为空但右节点不为空，则返回右节点给根节点；如果节点的右节点为空但左节点不为空，则返回左节点给根节点。如果左右都为空，则将空传入根节点。如果左右都不为空，根节点不变，也就是将根节点返回给根节点，等待下一次循环对根节点的判断。