题干：

代码：

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

思考：回溯思想总与二叉树的后序遍历挂钩；递归的return 不应该将其看为一个值，而应该是一个“响应”，来传递有没有找到信息。譬如：

if(root == p || root == q)return root;//意思是遇到p或q了，要将遇到pq的消息返回给上一层

这一行代码与下面五行相挂钩：

if(left != NULL && right != NULL)return root;//说明找到了pq，直接返回pq的root
else if(left != NULL && right == NULL)return left;//说明右边找不到pq而左边可以，将左向上返回
else if(left == NULL && right != NULL)return right;//说明左边找不到pq而右边可以，将右向上返回
else return NULL;//左右都为空，返回空