这是悦乐书的第197次更新，第203篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第59题（顺位题号是235）。给定二叉搜索树（BST），找到BST中两个给定节点的最低共同祖先（LCA）。根据维基百科上LCA的定义：“最低共同祖先在两个节点p和q之间定义为T中的最低节点，其中p和q都是后代（我们允许节点成为其自身的后代）。”
给定二叉搜索树：root = [6,2,8,0,4,7,9，null，null，3,5]
6
/ \
2 8
/ \ / \
0 4 7 9
/ \
3 5例如：
输入：root = [6,2,8,0,4,7,9，null，null，3,5]，p = 2，q = 8
输出：6
说明：节点2和8的LCA为6。
输入：root = [6,2,8,0,4,7,9，null，null，3,5]，p = 2，q = 4
输出：2
说明：节点2和4的LCA是2，因为节点可以是其自身的后代，根据LCA的定义。
注意：
-
所有节点的值都是唯一的。
-
p和q不同，两个值都将存在于BST中。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
利用迭代的方法。二叉搜索树的特点是 左节点的值 < 根节点的值 < 右节点的值，如果p和q的节点值都小于当前节点，此时指针应该移动到当前节点的左节点，再去比较。如果p和q的节点值都大于当前节点，此时指针应该移动到当前节点的右节点，再去比较。否则就返回当前节点。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (p.val < root.val && q.val < root.val) {
root = root.left;
} else if (p.val > root.val && q.val > root.val) {
root = root.right;
} else {
return root;
}
}
return root;
}03 第二种解法
利用递归的方法，判断逻辑和迭代的解法一样。如果当前节点的值比p和q中最大值都要大，因为当前节点的左子节点值肯定小于当前节点的值，所以要往当前节点的左子节点方向移动。如果当前节点的值比p和q中最小值都要小，因为当前节点的右子节点值肯定大于当前节点的值，所以要往当前节点的右子节点方向移动。然后再去判断。
public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (root.val > Math.max(p.val, q.val)) {
return lowestCommonAncestor2(root.left, p, q);
}
if (root.val < Math.min(p.val, q.val)) {
return lowestCommonAncestor2(root.right, p, q);
}
return root;
}04 小结
算法专题目前已连续日更超过一个月，算法题文章59+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
转载于:https://www.cnblogs.com/xiaochuan94/p/10094634.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/101273.html原文链接：https://javaforall.net
