236. Lowest Common Ancestor of a Binary Tree

Question

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

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 the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

    _______3______
   /              \
___5__          ___1__    /      \        /      \    6      _2       0       8
     /  \
     7   4

Example 1:

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

Example 2:

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

Thinking:

Method 1:递归

/**
 * 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 inLeft = contains(root.left, p);
        boolean inRight = contains(root.right, q);
        if((inLeft && inRight) || (!inLeft && !inRight)) return root;
        else if(inLeft && !inRight) return lowestCommonAncestor(root.left, p, q);
        else if(inRight && !inLeft) 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:减少递归的次数。

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

二刷

Same as previous quesiton, I just copy and paste.

/**
 * 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);
 }
}

I modified the result a little bit and get a result.

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

 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);
 }
}

Method 3, it is using divide and conquer method.
- We first find their common ancestor in left child. Result is A.
- Then we find their common ancestor in right child. Result is B.
- if A and B are both not null, it means current node is their closest common ancestor.
- if one of them is not null, the other one is their closest common ancestor. ```Java /**
- 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 == p || root == q || root == null) return root; TreeNode left = lowestCommonAncestor(root.left, p ,q); TreeNode right = lowestCommonAncestor(root.right, p ,q); if(left != null && right != null){ return root; }else if(left != null) return left; else if(right != null) return right; return null; } } ```

Amazon session

Method 1:divide and conquer ```Java /**
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 || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); //left subtree contains p or q and right subtree contains p or q if(left != null && right != null) return root; // right is null and left contains both. else if(left != null) return left; // left contains both. else if(right != null) return right; return null; } } ```