刷代码随想录有感（58）：二叉树的最近公共祖先

题干：

代码：

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;//左右都为空，返回空