LeetCode-Lowest Common Ancestor of a Binary Search Tree

￡神魔★判官ぃ 2022-08-09 10:00 41阅读 0赞

**Problem:**  
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”  
![这里写图片描述][20151020201703514]  
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

**Analysis:**  
这个是二叉搜索树的题，根据二叉搜索树的特点可知：

root.val<root.right.val  且 root.left.val<root.val

那么我们只要判断p和q是否在root的左右分支或者p和q中的一个是root即可。  
但是p和q哪个大并不清楚，这里有个**绝招**：

(root.val-p.val)*(root.val-q.val)<=0

**Anwser1:** 利用死**循环查找**

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            while(root!=null){
                if((root.val-p.val)*(root.val-q.val)<=0) return root;
                else if(root.val>p.val) root=root.left;
                else root=root.right;
            }
            return null;
        }
    }

**Anwser2:** 利用**递归查找**

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
                if((root.val-p.val)*(root.val-q.val)<=0) return root;
                else if(root.val>p.val) return lowestCommonAncestor(root.left,p,q);
                else return lowestCommonAncestor(root.right,p,q);
        }
    }

[20151020201703514]: /images/20220731/4729ce8a43b743be903bdb12c576941a.png