二叉树：公共祖先问题( 二 ) 本来是打算将二叉树和二叉搜

「如果left为空， right不为空，就返回right ，说明目标节点是通过right返回的，反之依然」。
这里有的同学就理解不了了，为什么left为空， right不为空，目标节点通过right返回呢？
如图：
文章插图
图中节点10的左子树返回null ，右子树返回目标值7 ，那么此时节点10的处理逻辑就是把右子树的返回值（最近公共祖先7）返回上去！
这里点也很重要，可能刷过这道题目的同学，都不清楚结果究竟是如何从底层一层一层传到头结点的。
【二叉树：公共祖先问题】那么如果left和right都为空，则返回left或者right都是可以的，也就是返回空。
代码如下：
if (left == NULL else if (left != NULL else{ //(left == NULL }那么寻找最小公共祖先，完整流程图如下：
文章插图
「从图中，大家可以看到，我们是如何回溯遍历整颗二叉树，将结果返回给头结点的！」
整体代码如下：
class Solution {public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == q || root == p || root == NULL) return root;TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);if (left != NULLif (left == NULLelse if (left != NULLelse{ //(left == NULL}}};稍加精简，代码如下：
class Solution {public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == q || root == p || root == NULL) return root;TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);if (left != NULLif (left == NULL) return right;return left;}};总结这道题目刷过的同学未必真正了解这里面回溯的过程，以及结果是如何一层一层传上去的。
「那么我给大家归纳如下三点」：

求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从低向上的遍历方式。
在回溯的过程中，必然要遍历整颗二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
要理解如果返回值left为空， right不为空为什么要返回right ，为什么可以用返回right传给上一层结果。

可以说这里每一步，都是有难度的，都需要对二叉树，递归和回溯有一定的理解。
本题没有给出迭代法，因为迭代法不适合模拟回溯的过程。理解递归的解法就够了。
「就酱，转发给身边需要学习的同学吧！」
-------end-------
我将算法学习相关的资料已经整理到了
Github ：，里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图，可以fork到自己仓库有空看一看一定会有所收获，顺便给一个star支持一下吧！
我是程序员Carl ，哈工大师兄，先后在腾讯和百度打杂，这里每天8:35准时推送一道经典算法题目，我选择的每道题目都不是孤立的，而是由浅入深，环环相扣，帮你梳理算法知识脉络，轻松学算法！
@代码随想录期待你的关注