讨论/《图解算法数据结构》 - 剑指 Offer 68 - II. 二叉树的最近公共祖先/
《图解算法数据结构》 - 剑指 Offer 68 - II. 二叉树的最近公共祖先
class Solution {
    TreeNode ans = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        isExist(root, p, q);
        return ans;
    }
    
    public boolean isExist(TreeNode root, TreeNode p, TreeNode q){
        if(root == null)    return false;
        boolean x = isExist(root.left, p, q); // 左子树存在p 或者 q
        boolean y = isExist(root.right, p, q);// 右子树存在p 或者 q
        // 左子树和右子树都存在p 或者 q
        // 当前节点为p 或者q 且左子树或者右子树存在另一节点
        if((x&&y) || ((root == p || root == q)&&(x||y))){   
            ans = root;
        }
        return x||y || root == p || root == q;
    }
}
2
展开全部 4 讨论