235. Lowest Common Ancestor of a Binary Search Tree

235. Lowest Common Ancestor of a Binary Search Tree

Question

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]

    _______6______
   /              \
___2__          ___8__    /      \        /      \    0      _4       7       9
     /  \
     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.

Thinking:

• Method 1：不利用bst的性质，单纯的找到最近公共结点。

/**
 * 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;
        if(root == q || root == p) return root;
        boolean pinLeft = contains(root.left, p);
        boolean pinRight = contains(root.right, p);
        boolean qinRight = contains(root.right, q);
        boolean qinLeft = contains(root.left, q)
        if(pinLeft && qinRight) return root;
        else if(pinRight && qinLeft) return root;
        else if(pinLeft && qinLeft) return lowestCommonAncestor(root.left, p, q);
        else if(pinRight && qinRight) return lowestCommonAncestor(root.right, p, q);
        return null;
    }
    private boolean contains(TreeNode root, TreeNode node){
        if(root == null) return false;
        if(root == node) return true;
        return contains(root.left, node) || contains(root.right, node);
    }
}

• Method 2: 利用BST的性质

/**
 * 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;
        if(p.val < root.val && q.val < root.val)
            return lowestCommonAncestor(root.left, p, q);
        else if(p.val > root.val && q.val > root.val)
            return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

二刷

1. Same thing as Method1

   /**
    * 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(p == root || q == root) return root;
        boolean pInLeft = isChild(root.left, p);
        boolean pInRight = isChild(root.right, p);
        boolean qInLeft = isChild(root.left, q);
        boolean qInRight = isChild(root.right, q);
        if(pInLeft && qInLeft){
            return lowestCommonAncestor(root.left, p, q);
        }else if(pInRight && qInRight){
            return lowestCommonAncestor(root.right, p, q);
        }else{
            return root;
        }
    }
   
    private boolean isChild(TreeNode node, TreeNode p){
        if(node == null) return false;
        if(node == p) return true;
        return isChild(node.left, p) || isChild(node.right, p);
    }
   }
   

2. Different from the previous method, we can use the property of BST and check isChild by just comparing the value, and even can check if current node is in left or right child node of current node.

   /**
    * 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;
        if(root.val == p.val || root.val == q.val) return root;
        else if(p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
        else if(p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
        else return root;
    }
   }
   

Amazon session

/**
 * 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 || p == null || q == null) return null;
        if(root == p || root == q) return root;
        boolean pVal = p.val < root.val;
        boolean qVal = q.val < root.val;
        if(!(pVal && qVal) && (pVal || qVal)) return root;
        else if(pVal) return lowestCommonAncestor(root.left, p, q);
        else return lowestCommonAncestor(root.right, p, q);
    }
}