236. Lowest Common Ancestor of a Binary Tree.md

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

二刷

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

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

3. 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.

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

Third Time

• Method 1: Divide and Conquer

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