LeetCode日记–235. Lowest Common Ancestor of a Binary Search Tree

发布于 2020-09-27  114 次阅读


碎碎念:买了个罗技的iPad键盘,以后就是iPad生产力的天下了,主要是K480太重了,不然其他的其实还是蛮不错的啦。

题目如下:

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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree:  root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

思路:

其实理解了二叉搜索树的概念以后,这道题是比较容易的。

这道题要求的是 Lowest Common Ancestor , 从定义可以知道,两个数的最低共同祖先,其实就是对于两数来说,把他们分在不同子树上的分界点。再结合二叉搜索树的定义可以知道,我们要找的LCA其实就是第一个搜到的,数值在输入的两节点之间(因为给出的数值本身也可以是LAC,所以是闭区间)。

那么代码如下:

我一开始的代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)
            return null;
        while(root!=null){
            if(between(root.val,Math.min(p.val,q.val),Math.max(p.val,q.val)))
                return root;
            else if(root.val<Math.min(p.val,q.val))
                root = root.right;
            else if(root.val>Math.max(p.val,q.val))
                root = root.left;
        }
        return root;
    }
    public static boolean between(int i, int minValueInclusive, int maxValueInclusive) {
    if (i >= minValueInclusive && i <= maxValueInclusive)
        return true;
    else
        return false;
}
}

但是后来一想,用between函数比较的结果,不就是前面两个情况的补集吗?所以改了一下,把调用函数取消了(但是发现时间和空间开销都没有发生什么变化)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)
            return null;
        while(root!=null){
            // if(between(root.val,Math.min(p.val,q.val),Math.max(p.val,q.val)))
            //     return root;
            if(root.val<Math.min(p.val,q.val))
                root = root.right;
            else if(root.val>Math.max(p.val,q.val))
                root = root.left;
            else
                return root;
        }
        return root;
    }

结果在瞎逛评论区的时候,发现一种递归的解法,时间开销上竟然比迭代快了1ms。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int v=root.val;
        if(p.val>q.val){
            TreeNode t=p;
            p=q;
            q=t;
        }
        int pV=p.val;
        int qV=q.val;
        if(pV<=v&&qV>=v){return root;}
        else if(v<=pV){return lowestCommonAncestor(root.right,p,q);}
        return null;       
    }
}

你好哇!欢迎来到雷公马碎碎念的地方:)