二叉搜索树的最近公共祖先

 
对于二叉搜索树，设两个节点的最近公共祖先为节点X，那么必有X的值介于两个节点的值之间，而且仅有一个节点满足条件。
 
基于这个条件，我们可以从根节点开始往下查找，思路就和二叉搜索树查找节点的思路类似。如果当前节点值比两个节点都大，则进入左子树，如果当前节点值比两个节点都小，则进入右子树。如果当前节点值介于两个节点之间，说明找到了最近公共祖先。伪代码如下：
 
1 // 默认p的值小于q的值，需要在输入前调整
2 lowestCommonAncestor(root, p, q)
3     if root.val < p.val and root.val < q.val
4         return lowestCommonAncestor(root.left, p, q)
5     else if root.val > p.val and root.val > q.val
6         return lowestCommonAncestor(root.right, p, q)
7     else
8         return root

二叉树的最近公共祖先

对于二叉树而言，因为没有节点的值之间的大小关系进行判断，所以不能选择只进入一个子树，需要两个子树都进入获取信息，然后再进行后续判断。
 
算法思路：
假设输入的两个节点为p节点和q节点，我们首先判断根节点是否是输入的两个中的一个。如果是的话，肯定就是最近公共祖先节点了，直接返回。如果不是的话，则需要进入两个子树查找。
 
往下查找的过程中如果当前节点为两个节点之一，则直接返回。如果不是的话，对左子树递归操作得到返回值为L，对右子树递归操作得到的返回值为R。这里根据L，R关系返回不同结果。
　　如果L和R均不为null，表示左子树和右子树都至少存在p和q中的一个，则该节点为最近公共祖先节点，可以返回当前节点
　　如果L和R中的一个为null，表示一个子树至少有p和q中的一个（如果包含两个，则L和R必是公共祖先)。可以直接返回L或R。
　　如果L和R都为null，表示两颗子树都没找到p或q。可以返回null。
　　注：这里返回null的情况表示以当前节点往下查找，找不到p和q的最近公共父节点，不表示整棵树中不存在。还要注意root为null时，显然当前节点往下找没有结果，可以直接返回null。
 
根据以上思路，可以写出伪代码：
 
 1 lowestCommonAncestor(root, p, q)
 2     // 如果root为null，没有找的必要，直接返回null
 3     if root = null
 4         return null
 5     // 如果root为其中一个，表示从root出发找到的最近公共祖先节点有的话只可能是root    
 6     if root = p or root = q
 7         return root
 8         
 9     // 对左子树和右子树递归操作    
10     L <- lowestCommonAncestor(root.left, p, q)
11     R <- lowestCommonAncestor(root.right, p, q)) 
12    
13    // 如果L和R都不为null,表示当前节点就是最近公共祖先节点
14    if L ≠ null and R ≠ null
15        return root
16    else if L = null and R ≠ null
17        return R           // 以root节点往下找，如果有目标节点的话只可能是R
18    else if L ≠ null and R = null
19        return L           // 以root节点往下找，如果有目标节点的话只可能是L 
20    else 
21        return null        // L和R都为null，都没找到

 

版权声明：本文为ningbing原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/ningbing/p/14824683.html