給一棵二叉樹和二叉樹中的兩個節(jié)點(diǎn)，找到這兩個節(jié)點(diǎn)的最近公共祖先LCA旨枯。
兩個節(jié)點(diǎn)的最近公共祖先趟佃，是指兩個節(jié)點(diǎn)的所有父親節(jié)點(diǎn)中（包括這兩個節(jié)點(diǎn)）耸袜，離這兩個節(jié)點(diǎn)最近的公共的節(jié)點(diǎn)友多。
返回 null 如果兩個節(jié)點(diǎn)在這棵樹上不存在最近公共祖先的話。
樣例
樣例1
輸入:
{4, 3, 7, #, #, 5, 6}
3 5
5 6
6 7
5 8
輸出:
4
7
7
null
解釋:
4
/ \
3 7
. . / \
. . 5 6
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
LCA(5, 8) = null

實(shí)現(xiàn)：

public class Solution {
    /*
     * @param root: The root of the binary tree.
     * @param A: A TreeNode
     * @param B: A TreeNode
     * @return: Return the LCA of the two nodes.
     */

    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        boolean existA = isNodeInTree(root, A);
        boolean existB = isNodeInTree(root, B);
         if (!existA || !existB) {
            return null;
        }
      
        return getLowestAncestor(root,A,B);
    }
    
    public TreeNode getLowestAncestor(TreeNode root, TreeNode A, TreeNode B){
        if (root == null || A == null || B == null) return null;
        if (root == A || root == B) return root;
        TreeNode left =  getLowestAncestor(root.left, A, B);
        TreeNode right = getLowestAncestor(root.right, A, B);
        if (left != null && right != null) {
            return root;
        }

        if (left != null) {
            return left;
        }
        if (right != null) {
            return right;
        }
        return null;
        
    }
     private  boolean isNodeInTree(TreeNode root, TreeNode node) {
        if (root == null || node == null) return false;
        if (root == node) return true;
        boolean left = isNodeInTree(root.left, node);
        boolean right = isNodeInTree(root.right, node);
        return left || right;
    }

}