广西网站建设原创,西安计算机培训机构排行榜,朝阳网站推广,微信制作小程序的软件今天是第 天刷leetcode#xff0c;立个flag#xff0c;打卡60天#xff0c;如果做不到#xff0c;完成一件评论区点赞最高的挑战。
算法挑战链接
235. 二叉搜索树的最近公共祖先https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/descriptio…今天是第 天刷leetcode立个flag打卡60天如果做不到完成一件评论区点赞最高的挑战。
算法挑战链接
235. 二叉搜索树的最近公共祖先https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
第一想法
题目理解从两个节点向上找汇聚的第一个节点。 如果两个节点分别是 45那么5向上找一位就是4.
如果两个节点分别是05那么他们会在2汇聚。
如果两个节点分别是57那么他们会在节点6汇聚。
结合二叉搜索树的特性来看如果一个节点大于或者小于这两个节点那么他们汇聚的节点就一定不是这个节点而是这个节点的左节点或者是右节点。
因此代码就很好写了只要这个两个节点都大于该节点就往该节点的右边遍历如果这个两个节点都小于该节点就往该节点的左边遍历。直到找到一个节点不满足都大于或者小于这两个节点的节点返回该节点。代码如下
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while (true) {if (root.val p.val root.val q.val) {root root.left;} else if (root.val p.val root.val q.val) {root root.right;} else {break;}}return root;}
}
看完代码随想录之后的想法
想法是一致的还有一种是递归的方法想法都是一样的。
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root.val p.val root.val q.val) return lowestCommonAncestor(root.left, p, q);if (root.val p.val root.val q.val) return lowestCommonAncestor(root.right, p, q);return root;}
}实现过程中遇到哪些困难
无
今日收获
二叉搜索树遍历如果是需要有序的那么是不需要排序的。
