江苏龙网

  1. 首页 > 人文 > >

二叉树：公共祖先问题( 二 )


如图：
二叉树：公共祖先问题文章插图
就像图中一样直接返回7 ， 多美滋滋 。
但事实上还要遍历根节点右子树（即使此时已经找到了目标节点了） ， 也就是图中的节点4、15、20 。
因为在如下代码的后序遍历中 ， 如果想利用left和right做逻辑处理 ，不能立刻返回 ， 而是要等left与right逻辑处理完之后才能返回 。
left = 递归函数(root->left);right = 递归函数(root->right);left与right的逻辑处理;所以此时大家要知道我们要遍历整棵树 。 知道这一点 ， 对本题就有一定深度的理解了 。
那么先用left和right接住左子树和右子树的返回值 ， 代码如下：
TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);「如果left 和 right都不为空 ， 说明此时root就是最近公共节点 。 这个比较好理解」
「如果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;}};总结这道题目刷过的同学未必真正了解这里面回溯的过程 ， 以及结果是如何一层一层传上去的 。
「那么我给大家归纳如下三点」：

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


    推荐阅读


上一篇：使用nginx反向代理github

下一篇：MoocDownloader，解锁中国大学慕课，课程免费送