腾讯精选50题算法【二叉搜索树的最近公共祖先】

  • 2019 年 12 月 25 日
  • 筆記

最近几周掺杂着需求、以及一些琐碎的事情，算法的学习一直都是默默的在搞，没有形成文章。

或许是我懒惰了；或许是我松懈了；或许是我不重视了；但是，我还在。学习可能会因为工作推迟，但绝不会迟到，所以，还请各位放心，该有的都会到来。为了补偿下，文末送个双十二大福利，知识星球优惠券

之前也在有些群里看到算法的持续学习，我自己又找了一个方式来攻克LeetCode上的题目，先从腾讯精选练习（50题） 开始，之前有完成过一些，不过都是整合在ARTS打卡里，也没细说。现在是一个系列，还有机会学习哒。

Algorithm LeetCode算法

235. 二叉搜索树的最近公共祖先 (https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)

题目描述：给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

      6     /        2      8   /     /    0   4  7    9     /     3   5

示例1：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8  输出: 6  解释: 节点 2 和节点 8 的最近公共祖先是 6。




示例2：




输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4  输出: 2  解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。


在题解之前，我们还是有必要知道二叉搜索树是一颗什么样的树，都有什么特点。








二叉搜索树（Binary Search Tree），又（二叉查找树，二叉排序树）它或者是一颗空树，或者是具有下列性质的二叉树：






    

  1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    2. 

  2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    3. 

  3. 它的左、右子树分别为二叉排序树。
    4. 



最近公共祖先： 是距离两个节点最近的公共祖先节点。在这里最近考虑的是节点的深度。


比如，在我们这颗二叉树中


    

  1. 如果p是2，q是8的情况，分别在跟节点的左右两边，则最近的公共节点就是他们的根节点，即6；
    2. 

  2. 如果p是2，q是7的情况，因为还是分别在6这个根节点的左右两边，那最近的公共节点还是6；
    3. 

  3. 如果p是2，q是4的情况，2和4在节点2的右子树上，即最小公共节点就是2自己了（一个节点也可以是它自己的祖先）
    4. 

  4. 如果p是2，q是0的情况，2和0在节点2的左子树上，即最小公共节点还是2自己
    5. 



好了，搞清楚了各种情况，接下来的解法肯定就难不倒我们了。写代码是建立在思路清晰的基础上，对吧。








解法：递归






    

  1. 从根节点开始遍历
    2. 

  2. 倘若p和q都在右子树上，则以右孩子为根节点继续1的操作
    3. 

  3. 倘若p和q都在左子树上，则以左孩子为根节点继续1的操作
    4. 

  4. 如果步骤2和步骤3均不成立，则说明我们已经找到答案
    5. 



将二叉树构建完成：


// 将二叉树构建完成  public static void main(String[] args) {      TreeNode treeNode = new TreeNode(6);      treeNode.left = new TreeNode(2);      treeNode.left.left = new TreeNode(0);      treeNode.left.right = new TreeNode(4);      treeNode.left.right.left = new TreeNode(3);      treeNode.left.right.right = new TreeNode(5);        treeNode.right = new TreeNode(8);      treeNode.right.left = new TreeNode(7);      treeNode.right.right = new TreeNode(9);        TreeNode treeNode2 = lowestCommonAncestor(treeNode, new TreeNode(2), new TreeNode(8));      System.out.println(treeNode2);  }


递归查找二叉树：


public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {      int parent = root.val;        int pValue = p.val;        int qValue = q.val;        // 如果两个值都大于跟节点，则从右子树查找      if (pValue > parent &&qValue > parent) {          return lowestCommonAncestor(root.right, p, q);      // 如果两个值都小于跟节点，则从左子树查找      } else if (pValue < parent && qValue < parent) {          return lowestCommonAncestor(root.left, p, q);      // 上述两种情况均没有，则得到答案      } else {          return root;      }  }


这里仅仅举例说明了通过递归的方式来解题，基本上也都能解决二叉树相关的问题。但是，就这样就够了吗？其实并没有，二叉树也有自己的特性，有时候是不需要通过递归来解决的。


在我们这个题解里，时间复杂度是O(N)，空间复杂度是O(N),时间复杂度没办法了，N是节点中的个数，在最坏的情况下我们是需要访问所有的节点，但是我们可以优化空间复杂度。








递归的时候，额外空间主要是栈产生的，N就是二叉树的高度，最坏情况下就是访问所有的，但是我们可以通过另一种方式来优化，空间复杂度可以达到O(1)。欢迎在留言区和我互动，至于写法，我会在知识星球给出，加入星球的小伙伴直接去看就行啦。


结语


二叉搜索树，算是对二叉树的一个延伸了，但是呢，解题的思路还是大同小异，无非就是二叉搜索树更加有自己的特点，我们操作起来反而会目的性更明确一些，也更好去理解。


LeetCode真的是一个好的学习社区，无论在谁的眼里，都是学习算法的好去处。小编也无数次的说过，算法就是一个持续学习的过程，只要持续学习，持续练习，持续写代码，你就能懂其中的解法，对于我们程序员的思维来说，是一个极大的提升，欢迎和大家一起学习。








插播一条


彪悍一只猫说过：他的很多次成为第一的经历，最主要的还是来自于社群的力量，如果没有来自社群的支持，他的推广能力是有限的，要想拿第一，真的很难。


所以，做好一个品牌，需要社群的力量，然后加上后期的IP推广。万事开头难，我现在需要的还是第一步，培养自己的社群，创造属于自己的一个小家庭，让每个人都有参与感，都能感受到存在的价值。


所以，在建立微信群的基础上，我也把星球建立起来了，就是为了和大家有更多的知识、职场等的交流。我个人还喜欢看球，还希望和大家一起聊聊球，畅所欲言呢。

		  				

		  				

													


						
						
						


						 

							
					

					    
									

													

													
											


			


			


	

		
VirMach 便宜 VPS
 


QNews
 
QNews