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

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

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

办法一：迭代

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

代码

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

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

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

2．返回值--最近公共先人 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)。

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

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

2．递推

1．开启左递归, 记为 left
2．开启右递归, 记为 right

3．返回值

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

4．当 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;
}