【算法训练-二叉树 五】【最近公共祖先】二叉树的最近公共祖先、二叉搜索树的最近公共祖先

public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        return dfsFindRoot(root, p, q);
    }
    private TreeNode dfsFindRoot(TreeNode node, TreeNode p, TreeNode q) {
        // 1 递归终止条件：越过叶子节点没找到;root为p或root为q
        if (node == null || node == p || node == q) {
            return node;
        }
        // 2 本级任务：分别在左右子树中寻找节点
        TreeNode left = dfsFindRoot(node.left, p, q);
        TreeNode right = dfsFindRoot(node.right, p, q);
        // 3 本级任务：分别在左右子树中寻找节点
        if (left != null && right != null) {
            //如果两个节点分别存在于左右子树，则当前节点即是最近公共祖先
            return node;
        }
        // 如果两个节点在root的同侧,则返回的节点即为公共节点
        if (right == null && left != null) {
            return left;
        }
        if (right != null && left == null) {
            return right;
        }
        // 如果两个节点左右都没有找到,则返回null
        return null;
    }

import java.util.*;
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        if (root == null) {
            return -1;
        }
        return dfsCheck(root, p, q);
    }
    private int dfsCheck(TreeNode node, int p, int q) {
        // 1 递归终止条件，找到了则返回值，超过叶子节点没找到则返回-1
        if (node == null) {
            return -1;
        }
        if ( node.val == p || node.val == q) {
            return node.val;
        }
        // 2 获取左右子树的查找结果
        int rightVal = dfsCheck(node.right, p, q);
        int leftVal = dfsCheck(node.left, p, q);
        // 3 依据查找结果判断取值
        if (rightVal != -1 && leftVal != -1) {
            // p、q分别在左右子树，且都不作为公共祖先
            return node.val;
        } else if (rightVal == -1) {
            // 右子树没有找到，左子树找到了，则返回左子树找到的最近公共祖先
            return leftVal;
        } else if (leftVal == -1) {
            // 左子树没有找到，右子树找到了，则返回右子树找到的最近公共祖先
            return rightVal;
        } else {
            // 两边都没找到，返回-1；
            return -1;
        }
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // Base case: 如果当前节点为空或者等于p或q中的任意一个，直接返回当前节点
    if (root == null || root == p || root == q) {
        return root;
    }
    // 递归查找左子树和右子树
    TreeNode leftLCA = lowestCommonAncestor(root.left, p, q);
    TreeNode rightLCA = lowestCommonAncestor(root.right, p, q);
    // 如果左子树和右子树都找到了最近公共祖先，那么当前节点就是最近公共祖先
    if (leftLCA != null && rightLCA != null) {
        return root;
    }
    // 如果只在一侧找到了最近公共祖先，返回那一侧找到的结果
    return (leftLCA != null) ? leftLCA : rightLCA;
}