祖先
28_二叉树的最近公共祖先
236.二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 示例 1: 输入:ro ......
代码随想录算法训练营第二十二天 | 235. 二叉搜索树的最近公共祖先,701.二叉搜索树中的插入操作,450.删除二叉搜索树中的节点
一、235. 二叉搜索树的最近公共祖先 题目链接: LeetCode 235. 二叉搜索树的最近公共祖先 学习前: 思路: 对于二叉搜索树,root不为空时与p和q的关系有4种,分别对应返回 root<p && root<q 递归调用右孩子 rootp || rootq return root ro ......
算法学习Day21二叉搜索树、公共祖先
Day21二叉搜索树、公共祖先 By HQWQF 2024/01/03 笔记 530.二叉搜索树的最小绝对差 给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数,其数值等于两值之差的绝对值。 示例 1: 输入: root = [4,2,6,1,3] ......
代码随想录算法训练营第二十一天|530.二叉搜索树的最小绝对差,501.二叉搜索树中的众数,236. 二叉树的最近公共祖先
一、530.二叉搜索树的最小绝对差 题目链接: LeetCode 530.二叉搜索树的最小绝对差 学习前: 思路: 中序遍历(递归+迭代)。首先中序遍历,将数值按照递增的方式存储,然后再计算最小绝对差 学习后: 中序遍历+双指针。在中序遍历中,一直存在指针指向前序结点,故在遍历过程中就可计算最小绝对 ......
最近公共祖先模板(LCA)
include <bits/stdc++.h> using namespace std; struct LCA { int n; vector<int> dep; vector<vector<int>> e; vector<array<int, 21>> fa; LCA() {} LCA(int n ......
树链剖分——最近公共祖先(LCA)
N,M,S,分别表示树的结点个数、询问的个数和树根结点 理论时间复杂度上界就是O(2n+mlogn) const int N=500010; int n,m,s,a,b; vector<int> e[N]; int fa[N],son[N],dep[N],siz[N]; int top[N]; vo ......
一种简洁且常数较小的在线树上k级祖先求解.
起因是有人在la群问 已知u是v的祖先,求u到v路径上第一个点. 怎么写比较简单. 突然想起很久之前我在la板子上写过一个题解区里没有看到的简洁做法. 有一个不难证明的结论,一个节点u的k级祖先v对应深度的所有节点中dfn序中小于等于u的最后一个点. 考虑dfn序的性质,u一定在v所在的子树的这段区 ......
最近公共祖先
目录倍增法求 LCA倍增法实现 倍增法求 LCA 倍增法 倍增法(英语:binary lifting),顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理,大大地优化时间复杂度。 这个方法在很多算法中均有应用,其中最常用的是 RMQ 问题和求 LCA(最近公共祖先)。 实现 'f[x][i]' ......
P3379 【模板】最近公共祖先(LCA)
非常详细的题解见洛谷,个人见解见代码 #include<bits/stdc++.h> using namespace std; #define N 500005 vector<int> G[N];//链树,以链上的元素为根节点的树 void add(int x,int y) { G[x].push_ ......
最近公共祖先
#include<bits/stdc++.h> using namespace std; typedef long long ll; vector<ll> G[500000+10]; ll n,m,root; ll f[500000+10][20],dep[500000+10],lg[500000+ ......
二叉树的最近公共祖先
二叉树的最近公共祖先 概述 对于两个节点 \(u\)、\(v\),找到一个深度最大的 \(x\),\(x\) 是 \(u\) 、\(v\) 的祖先。 则 \(x\) 为这两个节点的最近公共祖先(LCA)。 初始方法 对于 \(u\) 或 \(v\): 从该结点一直向上找祖先,知道找到整棵树的根节点, ......
最近公共祖先(LCA)
最近公共祖先(LCA) 概念 在有根树中,两个点,会有共同的祖先,离他们两最近的公共祖先,即为LCA 求法 向上表记法O(n) 从一个点开始,向上遍历,把走过的点标记一下 再从另外一个点开始,向上遍历,如果走到的点已经被标记,即为LCA 最坏的情况是条链,\(O(n)\)的复杂度 倍增法 O(log ......
离线快速LCA(最近公共祖先) Tarjan算法
离线快速LCA(最近公共祖先) Tarjan算法 前言 对于 OIer 来说,LCA 一直是处理树上问题的好帮手,无论是倍增还是树剖都有着优秀的 \(\log n\) 的复杂度。不过由于我们(数据规模)的上进,需要更快速求 LCA,于是就有了…… 反正之前打死我都不相信这玩意能离线,还能 O(1) ......
代码随想训练营第二十二天(Python)| 235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点
235. 二叉搜索树的最近公共祖先 关键点:最近公共祖先的判断,二叉树的特性 1、做二叉树的模式 class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'Tr ......
力扣1026. 节点与其祖先之间的最大差值(DFS)
给定二叉树的根节点 root,找出存在于 不同 节点 A 和 B 之间的最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。 (如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先) 示例 1: 输入:root = [ ......
代码随想训练营第二十一天(Python)| 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先
二叉搜素树,利用中序遍历的升序结果 530.二叉搜索树的最小绝对差 1、递归中序遍历 class Solution: def __init__(self): self.pre = None self.res = float('inf') def getMinimumDifference(self, ......
【图论】最近公共祖先 学习笔记
LCA 基本概念 对于一个有根树,如果点 \(z\) 既是点 \(x\) 的祖先,又是点 \(y\) 的祖先,则说点 \(z\) 是 \(x\) 和 \(y\) 的公共祖先。每对点的所有公共祖先里,深度最大的那个点被称作这两个或多个点的最近公共祖先(lca)。 lca 有很多优秀的性质,例如经过 l ......
代码随想录day21 | ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先
530. 二叉搜索树的最小绝对差 class Solution { private: int result = INT_MAX; TreeNode* pre = NULL; void traversal(TreeNode* cur){ if (cur == NULL) return; travers ......
最近公共祖先 Tarjan算法
P3379 【模板】最近公共祖先(LCA) 利用并查集 点击查看代码 #include<bits/stdc++.h> using namespace std; const int N = 5e5 + 10; vector<int> g[N]; vector<pair<int,int>> query[ ......
最近公共祖先 倍增算法
P3379 【模板】最近公共祖先(LCA) 点击查看代码 #include<bits/stdc++.h> using namespace std; const int N = 5e5 + 10; vector<int> g[N]; int dep[N], fa[N][22]; void dfs(in ......
剑指 Offer 68 - II. 二叉树的最近公共祖先
题目链接: 剑指 Offer 68 - II. 二叉树的最近公共祖先 题目描述: 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 解法思路: 代码: /** * Definition for a binary tree node. * type TreeNode struct { * Va ......
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
题目链接: 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 题目描述: 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 解法思路: 代码: /** * Definition for a binary tree node. * type TreeNode struct { * ......
【模板】最近公共祖先LCA——倍增
题目来自洛谷P3379 【模板】最近公共祖先(LCA) 【模板】最近公共祖先(LCA) 题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 输入格式 第一行包含三个正整数 \(N,M,S\),分别表示树的结点个数、询问的个数和树根结点的序号。 接下来 \(N-1\) 行每行包含 ......
共同祖先
题目 https://kamacoder.com/problem.php?id=1010 小明发现和小宇有共同祖先!现在小明想知道小宇是他的长辈,晚辈,还是兄弟。 输入包含多组测试数据。每组首先输入一个整数N(N<=10),接下来N行,每行输入两个整数a和b,表示a的父亲是b(1<=a,b<=20) ......
26.二叉树的最近公共祖先
# 236.二叉树的最近公共祖先 ## 1、概要 > 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 > > 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖 ......
力扣---1123. 最深叶节点的最近公共祖先
给你一个有根节点 root 的二叉树,返回它 最深的叶节点的最近公共祖先 。 回想一下: 叶节点 是二叉树中没有子节点的节点 树的根节点的 深度 为 0,如果某一节点的深度为 d,那它的子节点的深度就是 d+1 如果我们假定 A 是一组节点 S 的 最近公共祖先,S 中的每个节点都在以 A 为根节点 ......
《剑指Offer》-68-二叉树的最近公共祖先
#### 二叉搜索树 ```cpp TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { // 如果p、q一定存在,那么root就一定不是空指针 TreeNode* traverse = root; wh ......
剑指 Offer 68 - II. 二叉树的最近公共祖先(简单)
题目: ![](https://img2023.cnblogs.com/blog/2679751/202308/2679751-20230826202719427-1395383638.png) ``` class Solution { public: TreeNode* lowestCommonA ......
代码随想录算法训练营第二十二天| 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点
235. 二叉搜索树的最近公共祖先 卡哥建议:相对于 二叉树的最近公共祖先 本题就简单一些了,因为 可以利用二叉搜索树的特性。 题目链接/文章讲解:https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%9 ......
二叉搜索树的公共祖先
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 1 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 2 if(root==nullptr||root==p||root==q)retur ......