BstLowestCommonAncestor
BstLowestCommonAncestor.java 源码
package algorithm.recursion;
/**
* @author roseduan
* @time 2020/9/24 9:11 下午
* @description 二叉搜索树的最近公共祖先
*/
public class BstLowestCommonAncestor {
/**
* 递归的方式
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right, p, q);
}
if (p.val < root.val && q.val < root.val){
return lowestCommonAncestor(root.left, p, q);
}
return root;
}
/**
* 递归改成循环
*/
public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (p.val > root.val && q.val > root.val) {
root = root.right;
} else if (p.val < root.val && q.val < root.val) {
root = root.left;
} else {
return root;
}
}
return null;
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
你可能感兴趣的文章
0
赞
热门推荐
-
2、 - 优质文章
-
3、 gate.io
-
6、 golang
-
7、 openharmony