首页 > 其他分享 >235. 二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先

时间:2023-04-11 17:25:14浏览次数:37  
标签:right TreeNode cur val 二叉 return 搜索 235 root

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

class Solution {
private:
    TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
        if (cur == NULL) return cur;
                                                        // 中
        if (cur->val > p->val && cur->val > q->val) {   // 左
            TreeNode* left = traversal(cur->left, p, q);
            if (left != NULL) {
                return left;
            }
        }

        if (cur->val < p->val && cur->val < q->val) {   // 右
            TreeNode* right = traversal(cur->right, p, q);
            if (right != NULL) {
                return right;
            }
        }
        return cur;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return traversal(root, p, q);
    }
//迭代法
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root) {
            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 return root;
        }
        return NULL;
    }
};

标签:right,TreeNode,cur,val,二叉,return,搜索,235,root
From: https://www.cnblogs.com/lihaoxiang/p/17306944.html

相关文章

  • 501. 二叉搜索树中的众数
    给你一个含重复值的二叉搜索树(BST)的根节点root,找出并返回BST中的所有众数(即,出现频率最高的元素)。如果树中有不止一个众数,可以按任意顺序返回。假定BST满足如下定义:结点左子树中所含节点的值小于等于当前节点的值结点右子树中所含节点的值大于等于当前节点的值左......
  • 15.6二叉排序树删除实战
    #include<stdio.h>#include<stdlib.h>typedefintKeyType;typedefstructBSTNode{KeyTypekey;structBSTNode*lchild,*rchild;}BSTNode,*BiTree;//非递归的创建二叉查找数intBST_Insert(BiTree&T,KeyTypek){BiTreeTreeNew=(BiTree)cal......
  • 15.5二叉排序树原理及建树实战
    #include<stdio.h>#include<stdlib.h>typedefintKeyType;typedefstructBSTNode{KeyTypekey;structBSTNode*lchild,*rchild;}BSTNode,*BiTree;//非递归的创建二叉查找数intBST_Insert(BiTree&T,KeyTypek){BiTreeTreeNew=(BiTree)cal......
  • 【剑指 Offer】 33. 二叉搜索树的后序遍历序列
    【题目】输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树:    5   /\  2  6 /\ 1  3示例1:输入:[1,6,3,2,5]输出:false示例2:输入:......
  • 二叉树的顺序存储
    二叉树的顺序存储二叉树的存储形式按照二叉树的结点层次编号,然依次后储存在数组当中二叉树的抽象数据类型表示二叉树顺序存储结构的示意图例题二叉树顺序存储结构的缺点1.顺序存储结构的大小固定不能动态的变化2.如果如图上为右单支树一样浪费空间所以顺序存储结构......
  • 搜索系统和推荐系统最大不同
     在脉脉上看到一个回答:1.搜索多了query,要保证内容相关性,容错率低;推荐容错率高,还需要一定的多样性和发现性。2.基于1,决定了搜索在召回阶段,兼顾相关行性和个性化,而推荐只需要个性化;在排序阶段,搜索目标是强偏序关系,识别物料的细微差别,通常用pairwise或listwise,推荐关心用户是否......
  • day 39 96. 不同的二叉搜索树
    给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。dp[3],就是元素1为头结点搜索树的数量+元素2为头结点搜索树的数量+元素3为头结点搜索树的数量元素1为头结点搜索树的数量=右子树有2个元......
  • ES搜索框架--自定义评分规则
    一、评分规则需求按照用户画像(不同的标签分数)和用户省份在用户查询时,对查询结果进行自定义评分二、ES自定义评分方式参考:博客:https://blog.csdn.net/W2044377578/article/details/128636611官网:https://www.elastic.co/guide/en/elasticsearch/guide/master/function-score-query.......
  • LeetCode 530.二叉搜索树的最小绝对值差
    1.题目:给你一个二叉搜索树的根节点root,返回树中任意两不同节点值之间的最小差值。差值是一个正数,其数值等于两值之差的绝对值。示例1:输入:root=[4,2,6,1,3]输出:1来源:力扣(LeetCode)链接:https://leetcode.cn/problems/minimum-absolute-difference-in-bst著作权归领扣网络所......
  • 分布式存储技术(下):宽表存储与全文搜索引擎的架构原理、特性、优缺点解析
    对于写密集型应用,每天写入量巨大,数据增长量无法预估,且对性能和可靠性要求非常高,普通关系型数据库无法满足其需求。对于全文搜索和数据分析这类对查询性能要求极高的场景也是如此。为了进一步满足上面两类场景的需求,有了宽表存储和搜索引擎技术,本文将对他们的架构、原理、优缺点做......