Leetcode-二叉搜索树最近公共祖先

梦里梦外; 2021-09-23 14:36 351阅读 0赞

**描述：给定一个二叉搜索树，找到该树中两个指定节点的最近公共节点（****最近公共祖先节点可以为节点本身）**

说明：所有节点的值都是唯一的。两个节点为不同节点且存在于给定的二叉搜索树。

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

首先复习一下二叉搜索树的性质：

1.   左子树上所有节点的值都小于等于根节点的值
2.   右子树上所有节点的值都大于等于根节点的值
3.   左子树和右子树也都是二叉搜索树

**方法一：递归**

1.   从根节点开始遍历树
2.  如果节点p和节点q都在右子树上，那么以右孩子为根节点继续1的操作
3.  如果节点p和节点q都在左子树上，那么以左孩子为根节点继续1的操作
4.  如果条件2和条件3都不成立，这意味着已经找到节点p和节点q的公共祖先了。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            int parentVal = root.val;
            int pVal = p.val,qVal = q.val;
            if (pVal > parentVal && qVal > parentVal) {
                return lowestCommonAncestor(root.right, p, q);
            } else if (pVal < parentVal && qVal < parentVal) {
                return lowestCommonAncestor(root.left, p, q);
            } else {
                return root;
            }
        }

递归算法是大家最熟悉的算法，也是第一时间想到的解决办法，下面介绍另外一种更加快捷方便的算法。

**方法二：清新脑回路 **

由二叉搜索树的特性可以知道，如果两个节点刚好位于左右子树，那么用根节点减去左子树乘以根节点减去右子树的乘积是小于等于0；所以由此特性可以写出更巧妙的算法：

public class LowestCommonAncestor_235 {
    
        private static TreeNode res = null;
        public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            lca(root, p, q);
            return res;
        }
    
        private static void lca(TreeNode root, TreeNode p, TreeNode q) {
            if ((root.val-p.val) * (root.val - q.val) <= 0) {
                res = root;
            } else if (root.val < p.val && root.val < q.val){
                lca(root.right, p , q);
            } else {
                lca(root.left, p , q);
            }
        }
    
        public static void main(String[] args) {
        }
    }

以上就是该算法的全部输出，有木有干货满满的样子。

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

辛苦各位大佬看完，有兴趣的可以关注下公众号（左），或者微信私信（右）共同学习进步；

![2019123122110235.jpg][]    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbnd1ZmVpeWFuZw_size_16_color_FFFFFF_t_70][]

[2019123122110235.jpg]: https://img-blog.csdnimg.cn/2019123122110235.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbnd1ZmVpeWFuZw_size_16_color_FFFFFF_t_70]: /images/20210923/5b8bf8d53d8f407999dd3894015c38ad.png