刷题专栏(十三):二叉搜索树的最近公共祖先

简介: 刷题专栏(十三):二叉搜索树的最近公共祖先

前言

刷题专栏到目前已经是第十三篇了,欢迎大家来关注我的刷题专栏,一起来刷题。

对了,依然是二叉树;这个数据结构真实博大精深。

可惜二叉树在日常增删改查编程中很少使用到,不然也不用这样单独刷二叉树的题目。

今天的这道《二叉树搜索树的最近公共祖先》一题,难度定义为简单,只要你对二叉树有基本的理解就可以解题成功。

一起来看看吧。

image.png

算法题:二叉搜索树的最近公共祖先

这道题目给出了三个初始的二叉树,是要让我们通过三个二叉树来得到一个结果。

第一个二叉树是总的树,暂时叫二叉搜索树。

第二个、第三个是条件树。

要根据两个条件树来获得二叉搜索树的一个节点。

虽然一般二叉树的处理使用递归即可,但是这次好像不是很行。

使用遍历的时候也要注意,是使用一次遍历还是两次遍历。

因为有两个条件树,这是一定要考虑在内的。

还是直接看代码吧。

代码逻辑展示

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }
}

代码执行结果

今天的这个结果,不是很满意,如果大家有什么更好方式能减少内存的消耗,评论区告诉我了。

image.png

总结

今天的这道题,主要是针对二叉树的一个反向逻辑,先找到一个值,然后找到这个值的前面的值。

所以除了要对二叉树数据结构有所了解,还要将这个逻辑搞清才行。

目录
打赏
0
0
0
0
2
分享
相关文章
|
9月前
|
【优选算法专栏】专题十八:BFS解决拓扑排序--前言
【优选算法专栏】专题十八:BFS解决拓扑排序--前言
73 1
|
9月前
|
实现单链表的基本操作(力扣、牛客刷题的基础&笔试题常客)
实现单链表的基本操作(力扣、牛客刷题的基础&笔试题常客)
221 38
|
9月前
|
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
70 0
|
9月前
|
刷题专栏(十一):二叉树的后序遍历
刷题专栏(十一):二叉树的后序遍历
69 0
|
9月前
|
刷题专栏(八):平衡二叉树
刷题专栏(八):平衡二叉树
60 0
|
9月前
|
刷题专栏(六):二叉树的最大深度
刷题专栏(六):二叉树的最大深度
68 0
|
9月前
|
刷题专栏(十二):翻转二叉树
刷题专栏(十二):翻转二叉树
77 0
|
9月前
|
刷题专栏(十):二叉树的前序遍历
刷题专栏(十):二叉树的前序遍历
64 0
牛客网《剑指offer》专栏刷题练习之二叉树合集
牛客网《剑指offer》专栏刷题练习之二叉树合集
100 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等