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