LeetCode：二叉树最低公共祖先

朱雀 2022-12-31 03:26 163阅读 0赞

二叉树最低公共祖先节点又是一道极为经典的算法题，LeetCode第236号题目，同时也是面试官几乎用烂的一个题目，准备跳槽找工作的同学必知必会的一个面试题。

这个题目的要求非常简单，求出给定两个二叉树节点的公共祖先，如下所示的二叉树，那么节点5和节点1的3，我们该怎样解决这个问题呢？

![format_png][]

####     ####

#### 如何确定两个节点的公共节点？ ####

这个问题的关键点在于我们怎么就能确定某个节点是给定条件下的公共节点，从图中我们能快速的知道节点5和节点1的公共节点是3，节点6和节点7的公共节点是5，问题是你有没有想过，**你的大脑是如何知道节点6和节点7的公共祖先是5的？**如果你能清晰的描述清楚这个过程，那么代码自然就能写出来了。

我们来看看为什么节点6和节点7的最低公共祖先是5。其实很简单，原因就在于**节点5和左子树中包含了节点6，节点5的右子树中包含了节点7**；也就是说只要我们找到了一个节点，其左右子树中分别包含了两个给定的节点，那么这个节点就是我们要找的答案。

意识到以上的关键就在于你要去想“为什么你的大脑知道节点6和节点7的公共祖先是5”，你的大脑是如何找到答案的？实际上你的大脑是这样找到答案的：

*  找到节点6的所有祖先节点，也就是5和3
 *  找到节点7的所有祖先节点，也就是2、5和3

那么很显然节点6和节点7的所有祖先节点从5开始就一样了，因此节点5就是最低公共节点，如图所示：

![format_png 1][]

此外我们还要考虑这样的特殊情况，那就是给定两个节点5和2，那么这两个节点的最低公共祖先节点是5，实际上这个特例并没有逃脱上述推导过程，你可以简单的认为一个节点的最低祖先其实是自己，由于节点5就是题目中给定的一个节点，而5的右子树中又包含2，那么5就是这两个节点的最低公共祖先。

现在让我们总结一下，什么样的节点才是我们需要找的最低公共祖先节点？

*  **如果一个节点的左子树和右子树分别包含了给定节点**，那么该节点就要找到的答案
 *  **如果一个节点本身就是题目给出的一个节点而且其左子树或者右子树包含另个一个给定节点**，那么该节点就是要找的答案

#### 代码实现 ####

有了上述结论，代码就非常简单啦，我们定义一个函数getLCA()， getLowestCommonAncestor的缩写，用于返回当前节点root的左子树(root->left)或者右子树(root->right)是否包含了题目中给定的两个节点，如果getLCA(root->left)和getLCA(root->right)返回的都是true，那么我们知道root就是所要找的最低公共祖先节点。

如果root本身就是给定的其中一个节点，那么只要getLCA(root->left)和getLCA(root->right)中的一个返回的是true，那么root就是所要找的最低公共祖先节点。

现在你该知道该怎么写代码了吧！

bool getLCA(TreeNode* root,
                TreeNode* p,
                TreeNode* q,
                TreeNode** res){
        if (root == NULL){
            return false;
        }
    
    
        bool l = getLCA(root->left, p, q, res);
        bool r = getLCA(root->right, p, q, res);
        if ((l && r) || 
            ((root == p || root == q) && (l||r))) {
            *res = root;
            return true;
        }
        return root == p || root == q || l || r;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root,
                                   TreeNode* p,
                                   TreeNode* q) {
        TreeNode* r= NULL;
        getLCA(root, p,q,&r);
        return r;
    }

这段代码非常简单，**核心仅仅只有8行代码**，这里向我们展示了只要问题分析的清楚明白，写代码实际上是一件水到渠成的事情。

#### 总结 ####

代码其实本质上只是一个从大脑的想法到机器能理解的**最细节的转化**，也就是说你首先要自己想明白，然后再通过代码告诉计算机让计算机也能明白，因此最关键还是要你自己清楚明白，如果一个问题对于你来说是模糊的不明确不清晰的，那么一定无法写出能正确运行的代码，因为计算机本身是最笨的机器，计算机不能理解“大概、可能、差不多”这些描述，计算机需要你精确的告诉它“是什么、是多少、怎么办”，因此如果你能正确的用代码来解决一个问题，那么你的大脑一定明白该如何解决这个问题。罗里吧嗦写了这些，重点是，动手写代码前你真的想明白该怎么解决问题了吗？

--------------------

**为你推荐**

<table> 
 <tbody> 
  <tr> 
   <td>1，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb986d1cbce0fc753efd9fef7497f1788c981f1769097754a7cdeeb8a9cb5c250d14166a215&amp;idx=2&amp;mid=2247483791&amp;scene=21&amp;sn=456e78baeea0f6cec222c0feea236863#wechat_redirect" rel="nofollow">彻底理解二叉树的遍历</a></td> 
  </tr> 
  <tr> 
   <td colspan="1">2，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98621cbce0f379a61fd68f64bed3e8e2d244235231786e908e7e0682cf349cda98edac7d0&amp;idx=1&amp;mid=2247483775&amp;scene=21&amp;sn=4dba79d9b015123ba58903086c9add60#wechat_redirect" rel="nofollow">彻底理解堆</a><br></td> 
  </tr> 
  <tr> 
   <td colspan="1">3，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98571cbce0c67abbced92c9b5eeacb59bdb44bab631fe73651105169ec7df571f4e59185d&amp;idx=1&amp;mid=2247483951&amp;scene=21&amp;sn=25ec562d60179985cba531dd8b06ae77#wechat_redirect" rel="nofollow">经典算法题：</a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98571cbce0c67abbced92c9b5eeacb59bdb44bab631fe73651105169ec7df571f4e59185d&amp;idx=1&amp;mid=2247483951&amp;scene=21&amp;sn=25ec562d60179985cba531dd8b06ae77#wechat_redirect" rel="nofollow">两个有序数组中位数</a></td> 
  </tr> 
  <tr> 
   <td colspan="1">4，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98603cbce0f151539b4123bc354c229ad911df4053b0cd72a805806486740892efc998259&amp;idx=1&amp;mid=2247483741&amp;scene=21&amp;sn=faf6b1e9e064389336546e7dcd555fd1#wechat_redirect" rel="nofollow">送命题：</a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98603cbce0f151539b4123bc354c229ad911df4053b0cd72a805806486740892efc998259&amp;idx=1&amp;mid=2247483741&amp;scene=21&amp;sn=faf6b1e9e064389336546e7dcd555fd1#wechat_redirect" rel="nofollow">进程切换与线程切换的区别</a><br></td> 
  </tr> 
  <tr> 
   <td colspan="1">5，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98548cbce0c5e054f9b90cd4004ff5d94b4ffedd87c86716b97de5aadcacf2de8dd4883b2&amp;idx=1&amp;mid=2247483926&amp;scene=21&amp;sn=a5f0097a10385a2ca6be8b9d1903e1b5#wechat_redirect" rel="nofollow">一道决定面试成败的算法题</a><br></td> 
  </tr> 
  <tr> 
   <td colspan="1">6，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb986a0cbce0fb64a2242783b4f52da4a1c141d606a3433f6a8e2584f59d10c76e7c41d5239&amp;idx=1&amp;mid=2247483902&amp;scene=21&amp;sn=4956ffd8d89934e8ec2c3e3e5f8ccb8b#wechat_redirect" rel="nofollow">一个耗时4小时的内存泄漏问题</a><br></td> 
  </tr> 
  <tr> 
   <td colspan="1">7，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98552cbce0c44953d79c8d0943aab40aeb9098eeffe533537ac9d23d17922b1826f83465c&amp;idx=1&amp;mid=2247483916&amp;scene=21&amp;sn=89851d1f4a6f53ed0308cd4a4da5881e#wechat_redirect" rel="nofollow">一个耗时36小时的内存异常问题</a><br></td> 
  </tr> 
  <tr> 
   <td colspan="1">8，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98571cbce0c67abbced92c9b5eeacb59bdb44bab631fe73651105169ec7df571f4e59185d&amp;idx=1&amp;mid=2247483951&amp;scene=21&amp;sn=25ec562d60179985cba531dd8b06ae77#wechat_redirect" rel="nofollow">LeetCode：</a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb98571cbce0c67abbced92c9b5eeacb59bdb44bab631fe73651105169ec7df571f4e59185d&amp;idx=1&amp;mid=2247483951&amp;scene=21&amp;sn=25ec562d60179985cba531dd8b06ae77#wechat_redirect" rel="nofollow">两个有序数组的中位数</a><br></td> 
  </tr> 
  <tr> 
   <td colspan="1">9，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb9856bcbce0c7de355c30b9b89ff7a56250324caa5b19f57e6423d6685c36707856c410798&amp;idx=1&amp;mid=2247483957&amp;scene=21&amp;sn=2637a7757351a3e8da0ae8a27488d295#wechat_redirect" rel="nofollow">LeetCode：</a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&amp;chksm=fcb9856bcbce0c7de355c30b9b89ff7a56250324caa5b19f57e6423d6685c36707856c410798&amp;idx=1&amp;mid=2247483957&amp;scene=21&amp;sn=2637a7757351a3e8da0ae8a27488d295#wechat_redirect" rel="nofollow">堆叠字符串</a><br></td> 
  </tr> 
 </tbody> 
</table>

![format_png 2][]

PS：微信公众号从去年开始限制了留言功能，如果你有任何问题欢迎直接在公众号留言。

[format_png]: /images/20221120/aaf3e3f3ab0645bea46ae3cf95b133b3.png
[format_png 1]: /images/20221120/1a27cb876bf14a8e8dd8a866916b6882.png
[format_png 2]: /images/20221120/c70a7ed6e1374ecdade19678833d5ac9.png