关于java:二叉搜索树的最近公共祖先和二叉树的最近公共祖先

１．二叉搜寻树的最近公共先人－－给定一个二叉搜寻树, 找到该树中两个指定节点(p&q)的最近公共先人(root)。

首先，咱们能够分为三种状况：
    １．指定节点散布在最近公共节点的两侧
    ２．p==root&&q在root的左右子树中
    ３．q==root&&p在root的左右子树中

办法一：迭代

１．循环搜寻　终止条件－－root为空
    １．p,q都在root的右子树中，则遍历root.right;
    ２．p,q都在root的左子树中，则遍历root.left;
    ３．否则找到，跳出

代码

public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
    while(root!=null){
        if(root.val<p.val && root.val<p.val){
                root=root.right;
        }else if(root.val>p.val && root.val>q.val){
                root=root.left;
        }else{
                return root;
        }
    }
    return root;
}

办法二：递归（集体感觉更好了解）
１．递推

   当p,q在同一侧开启递归

２．返回值－－最近公共先人root;
代码

public TreeNode lowestAncestor(TreeNode root,TreeNode p,TreeNode q){
    if(root.val<p.val && root.val<q.val){
        return lowestCommonAncestor(root.right,p,q);
    }
    if(root.val>pa.val && root.val>q.val){
        return 
        lowestCommonAncestor(root.left,p,q);
    }
    return root;
}

2．二叉的最近公共先人－－给定一个二叉树（留神和下面不一样，第一题是二叉搜寻树）, 找到该树中两个指定节点(p&q)的最近公共先人(root)。

和第一题一样三种状况
递归
１．终止条件：

１．当越过叶子节点，则间接返回null;
２．当root==p|| root==q ,返回root;

２．递推

１．开启左递归,记为left
２．开启右递归,记为right

３．返回值

    １．当left and right同时为空：不蕴含p和q,返回null;
    ２．当left and right同时不为空：阐明散布在异侧，返回root;
    ３．left为空，right不为空
            １．p,q其中一个在root的右子树中，此时right指向p;
            ２．p,q都在root的右子树中，此时指向最近公共节点 

４．当left不为空

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 null;}
if(left==null){
return right;}
if(right==null){
return left;}
return root;
}