天道酬勤,学无止境

Find all the ancestors of leaf nodes in a tree with pandas

I have a table that has two columns, 'parent' and 'child'. This is a download from SAP (ERP) for SETNODE table. Need to create a dataframe in python that has each level as it's own column in respect to it's parent and all levels before.

In python 3+.

There are an unknown (or always changing) number of levels for the full relationship so that max level can't always be defined. I would like to create a full dataframe table that shows ALL parent/child relationships for all levels. Right now it's about 15 levels but it can probably go up to 20 or more with other data I work with.

For example (example_df) of the two columns:

example_df = pd.DataFrame({'parent:['a','a','b','c','c','f'],'child':['b','c','d','f','g','h']})

To give output dataframe (solution_example):

solution_example = pd.DataFrame({'child':['h','f','d'],'parent_1':['a','a','a'],'parent_2':['c','c','b'],'parent_3':['f', 'none', 'none']})

评论

This can be solved using the networkx library. First, build a directed graph from the DataFrame, and then find all ancestors of the leaf nodes.

import networkx as nx

leaves = set(df.child).difference(df.parent)
g = nx.from_pandas_edgelist(df, 'parent', 'child', create_using=nx.DiGraph())
ancestors = {
    n: nx.algorithms.dag.ancestors(g, n) for n in leaves
}

(pd.DataFrame.from_dict(ancestors, orient='index')
   .rename(lambda x: 'parent_{}'.format(x+1), axis=1)
   .rename_axis('child')
   .fillna(''))

      parent_1 parent_2 parent_3
child                           
h            a        c        f
g            a        c         
d            a        b         

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • 数据结构总结:各种树的定义
    术语 节点深度:对任意节点x,x节点的深度表示为根节点到x节点的路径长度。所以根节点深度为0,第二层节点深度为1,以此类推 节点高度:对任意节点x,叶子节点到x节点的路径长度就是节点x的高度 树的深度:一棵树中节点的最大深度就是树的深度,也称为高度 父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点 子节点:一个节点含有的子树的根节点称为该节点的子节点 节点的层次:从根节点开始,根节点为第一层,根的子节点为第二层,以此类推 兄弟节点:拥有共同父节点的节点互称为兄弟节点 度:节点的子树数目就是节点的度 叶子节点:度为零的节点就是叶子节点 祖先:对任意节点x,从根节点到节点x的所有节点都是x的祖先(节点x也是自己的祖先) 后代:对任意节点x,从节点x到叶子节点的所有节点都是x的后代(节点x也是自己的后代) 森林:m颗互不相交的树构成的集合就是森林 PS:其实对于祖先和后代的定义,不同的资料有不同的解释,争论在于节点本身是否是本身的祖先或者后代,我这里的定义取得是《数据结构与算法( Java 描述)-邓俊辉》。维基百科中对于祖先和后代的定义是: Descendant:A node reachable by repeated proceeding from parent to child. Ancestor:A node reachable by repeated
  • Hobbs' algorithm for Coref Resolution [closed]
    Closed. This question is off-topic. It is not currently accepting answers. Want to improve this question? Update the question so it's on-topic for Stack Overflow. Closed 8 years ago. Improve this question I have implemented Hobbs' algorithm for anaphora resolution together with Lappin & Leass ranking for alternatives. What bugs me is that the description of the algorithm is completely informal, and since there are sentences that are not correctly resolved by my implementation I am not sure whether the limit is on my implementation or on the actual algorithm. Here is the version I have worked
  • Finding best common ancestor of two leaf nodes where nodes have zero, one, or two parents
    Goal: I am looking for an algorithm to find the best common ancestor of a graph where nodes in the graph can have zero, one, or two parents. I am not sure of the terminology of "best common ancestor": better terminology might be "lowest common ancestor", or "recent common ancestor", etc. If there is better terminology then please provide URL's that describe such. The algorithm has access to the full graph data structure. It is possible for a given node to have zero, one, or two parents. This is key because the algorithms I've seen on the web assume that a given node has either zero or one
  • leetcode刷题目录
    leetcode大神 https://www.cnblogs.com/grandyang/p/4606334.html https://github.com/gzwl/leetcode https://blog.csdn.net/lanxu_yy/column/info/leetcode-solution 电子书下载 目标:在我职业生涯的前3年,至少把leetcode上的题刷完一半 刷题oj:https://www.luogu.com.cn/problem/list?orderBy=difficulty&order=asc&difficulty=1&page=1 排序 交换类排序 – 冒泡排序 鸡尾酒排序 奇偶排序 梳子排序 侏儒排序 快速排序 臭皮匠排序 Bogo 排序 选择类排序 – 选择排序 堆排序 Smooth 排序 笛卡尔树排序 锦标赛排序 圈排序 插入类排序 – 插入排序 希尔排序 二叉查找树排序 图书馆排序 耐心排序 归并类排序 – 归并排序 梯级归并排序 振荡归并排序 多相归并排序 Strand 排序 分布类排序 – 美国旗帜排序 珠排序 桶排序 计数排序 鸽巢排序 相邻图排序 基数排序 混合类排序 – Tim 排序 内省排序 Spread 排序 UnShuffle 排序 J 排序 Java如何生成长度为n,范围为[l, r]的随机整数数组 什么是稳定排序
  • Codeforces 1494D Dogeforces(构造+并查集)
    传送门 题目大意 给出一棵带权树,其中所有父节点的权值一定严格大于子节点。给出了所有叶子节点的权值以及两两叶子之间的 最近公共祖先 L C A LCA LCA 的权值,试着还原这棵树。 解题思路 树的构造问题大都从特殊到一般、从叶子结点开始构造。 对于两个叶子结点,显然第一次操作时只需要新建一个节点,然后将他们连接起来;对于两棵分别连好了两个叶子节点的子树,如下图所示,若 1 4 1~~4 1 4 的 L C A LCA LCA 的权值大于了两个父节点 5 , 6 5,6 5,6,那么我们新建一个 7 7 7 节点连接上这两棵子树。 这个时候似乎已经可以窥见构造规律了,对于每对给出的 L C A LCA LCA信息,从小到大构造。上述子树还会有两种情况,也就是当前的 L C A LCA LCA等于两棵子树的某个根节点,那么将另一棵子树连上去即可。至于如何维护一棵子树的根节点,使用并查集,但是并查集只是维护两个集合的,怎么保证集合的祖先就是根节点?实际上只需要设置当前集合祖先时更新为根节点,这样在路径压缩的时候祖先节点的信息不会改变,只会将下面子节点的祖先节点更新,真是妙用! 易错点: 对于一个节点的子树下若有很多节点,如何保证不生成两个相同的父节点(对于本题的贪心思路来说,尽可能使得相同的 L C A LCA LCA 连接到同一根节点下),那么对于相同的 L C A LCA LCA
  • 数据结构:树、查找二叉树、平衡树(AVL树)、伸展树(SplayTree)总结
    树 相关术语: root 根edge 边child 子节点parent 父节点leaf 叶节点sibling 兄弟节点path 路径:从节点n1 到 nk的路径定义为:节点n1 n2 n3 … nk 的序列, 使得对于1<=i<k的节点ni是ni+1的父节点。路径的长(length)即为该路径上的边的数量, 即k-1.depth 深度:从根节点到ni的唯一路径的长。特别的,根的深度为0.internal path length 内部路径长:一棵树的所有节点的深度的和称为内部路径长。height 高度:从ni到一片树叶的最长路径的长。特别的,叶节点的高度都为0.height of tree 树的高度:即根节点的高度depth of tree 树的深度:即树的最深的节点的深度(树的深度=树的高度)ancestor 祖先descendant 后裔proper ancestorproper descendantpreorder traversal 先序遍历:对节点的处理在对其子节点的处理之前postorder traversal 后序遍历:对节点的处理在对其子节点的处理之后inorder traversal 中序遍历:先处理左节点,再根节点,最后右节点(对于二叉树)level-order traversal 层序遍历:深度为D的节点要比深度为D+1的节点之前处理 相关结论:
  • 使用实体框架的最有效的自引用树方法(Most efficient method of self referencing tree using Entity Framework)
    问题 所以我有一个SQL表,基本上 ID, ParentID, MenuName, [Lineage, Depth] 最后两列是自动计算的,可帮助您进行搜索,因此我们现在可以忽略它们。 我正在创建一个具有多个类别的下拉菜单系统。 不幸的是,EF我认为自引用表的深度不能超过1级。 所以我有几个选择 1)创建查询,按深度排序,然后在C#中创建一个自定义类,一次填充一个深度。 2)找到一些渴望将数据加载到EF中的方法,我认为不可能有无限数量的级别,而只有固定数量的级别。 3)我什至不确定。 任何输入都将受到欢迎! 回答1 我已经使用EF成功映射了层次结构数据。 以Establishment实体为例。 这可以代表更大组织结构中的公司,大学或其他部门: public class Establishment : Entity { public string Name { get; set; } public virtual Establishment Parent { get; set; } public virtual ICollection<Establishment> Children { get; set; } ... } 这是父/子属性的映射方式。 这样,当您设置“父项为1”实体时,父项的“子项”集合将自动更新: // ParentEstablishment 0..1 <---> *
  • 红黑树深入剖析及Java实现
    红黑树是平衡二叉查找树的一种。为了深入理解红黑树,我们需要从二叉查找树开始讲起。BST二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找效率。在理想的情况下,二叉查找树增删查改的时间复杂度为O(logN)(其中N为节点数),最坏的情况下为O(N)。当它的高度为logN+1时,我们就说二叉查找树是平衡的。BST的查找操作T key = a search key Node root = point to the root of a BST while(true){ if(root==null){ break; } if(root.value.equals(key)){ return root; } else if(key.compareTo(root.value)<0){ root = root.left; } else{ root = root.right; } } return null;从程序中可以看出,当BST查找的时候,先与当前节点进行比较:如果相等的话就返回当前节点;如果少于当前节点则继续查找当前节点的左节点;如果大于当前节点则继续查找当前节点的右节点。直到当前节点指针为空或者查找到对应的节点,程序查找结束。BST的插入操作Node node = create a
  • 数据结构~12.树与二叉树
    数据结构学习~12.树与二叉树 本文是上一篇文章的后续,详情点击该链接~ 树的基本概念 树是一种非线性的数据结构。要理解树的概念及其术语的含义,用一个例子说明是最好的方法。就比如下图就是一棵树,它是若干节点的集合。是由唯一的根(A)和若干互不相交的子树。就比如说,A,D,H,M,I,J这六个结点组成的树就是一颗子树组成的。其中,每一棵子树又是一棵树,也是由唯一的根结点和若干棵互不相交的子树组成的。由此而知,树的定义是递归的,也就是在树的定义中又用到了树的定义。要注意的是,树的结点数目可以为0,当为0时,这棵树称为一颗空树。 树的基本术语 结点: 刚刚那棵树的A,B,C等都是结点,结点不仅包含数据元素,而且包含指向子树的分支。也就是说A的结点不仅包含数据元素A,而且包含三个指向子树的指针。 结点的度: 结点拥有的子树个数或者分支的个数称为结点的度。就比如说A结点有三棵子树,所以A结点的度为3 树的度 树中各结点度的最大值。比如说树的结点度最大为3(就像刚才那棵树的A结点),最小为0(就像是K,L,M等) 叶子结点 叶子结点又叫做终端结点,指度为0的结点,就比如刚才那棵树K,L,F,G,M,I,J都是叶子结点 非终端结点 非终端结点又叫做分支结点,指度不为0的结点,刚才那棵树除了叶子节点外,其他的都是非终端结点。除了根节点之外的非终端结点,也叫做内部结点。就像B,C,D,E
  • 四十行代码搞定经典的并查集算法
    今天是算法与数据结构的第18篇文章,我们一起来看一个经典的数据结构——并查集。 首先我们来解释一下这个数据结构的名称,并查集其实是一个缩写,并指的是合并,查指的是查找,集自然就是集合。所以并查集的全称是合并查找集合,那么顾名思义,这是一个用来合并、查找集合的数据结构。 并查集的定义 集合虽然是一个抽象的概念,但是生活当中关于集合的操作其实不少,只是我们身处其中的时候往往习以为常了。 举个例子,比如A和B两个人都是社会精英,两人名下都有一大笔资产。突然某一天,两个人宣布结婚了,那么很显然,一般情况下两个人的资产会被合并成夫妻共同财产。如果我们把他们两人的资产都看成是一个集合,那么结婚就会让这两个集合进行合并。再举一个例子,比如在古时候交通不便,河两岸的村庄往往很少来往。如果某一天河上建了一座桥,连通了河两岸,如果我们把两岸的紧密来往的村庄各自看成是一个集合,桥的建成显然也会让这两个集合合并。 上面的例子都是关于集合合并的, 关于集合查找的例子也很多。最经典的就是DNA检测,比如经常会有一些人号称自己是某某家族的后代。如果我们想要验证他们的身份最好的办法就是去查DNA谱系,我们人有一半的基因来自父亲,一半的基因来自母亲,这些基因也可以看成是集合。如果某个人号称是某朝皇室,我们把皇室的基因和他自己家族的基因一匹配,发现并非来自同一个集合,那么自然这些论调就不告而破了
  • 236.二叉树的最近公共祖先(java)
    236.二叉树的最近公共祖先 题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4] 示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 示例 2: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。 说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。 题解:递归 终止条件: 到达叶节点找到p或q点 递推工作: 左递归节点设置为left右递归节点设置为right 返回值 left、right为空,返回nullleft、right都不为空,此时根节点为公共祖先left为空,right不为空 p,q 其中一个在 rootroot 的 右子树 中,此时
  • SQL Server 中多对多层次结构的数据结构(Data structure for many to many hierarchies in SQL Server)
    问题 我的系统中已经有以下数据结构。 ItemDetails : ID Name -------- 1 XXX 2 YYY 3 ZZZ 4 TTT 5 UUU 6 WWW 并且层次结构在单独的表中(具有多对多关系) ItemHierarchy : ParentCode ChildCode -------------------- 1 2 1 3 3 4 4 5 5 3 5 6 如您所见,3 是 1 和 3 的子节点。我想遍历记录,例如来自节点 3 的记录。 我需要编写一个存储过程并获取3的所有祖先和3的所有子节点。 您能否让我知道是否有可能提取数据? 如果是这样,哪种数据结构适合它。 请注意,我的表包含 100 万条记录,其中 40% 具有多个层次结构。 我对级别进行了“CTE”,并根据层次结构对其进行了递增,但是当我们从根节点遍历到叶级别节点时,出现了最大递归错误。 我尝试过“HierarchyID”,但是当它有多个父节点时无法获取所有详细信息。 更新:我可以将递归限制设置为 max 并运行查询。 由于它有数百万行,我根本无法获得输出。 我想创建一个数据结构,使其能够从上到下或从下到上(在任何节点级别)提供信息。 有人可以帮助我吗? 回答1 不推荐使用 RDBMS 进行分层数据结构,这是创建图形数据库的原因。 顺便说一句,遵循闭包表模式会对您有所帮助。 Closure Table
  • leetcode刷题 二叉树 python
    目录 二叉树遍历 二叉树三种遍历递归 144.二叉树的前序遍历 非递归 94. 二叉树的中序遍历 非递归 145. 二叉树的后序遍历 非递归 104. 二叉树的最大深度 剑指 Offer 55 - I. 二叉树的深度 110. 平衡二叉树 剑指 Offer 55 - II. 平衡二叉树 124. 二叉树中的最大路径和 112. 路径总和 113. 路径总和 II 剑指 Offer 34. 二叉树中和为某一值的路径 二叉树框架 226. 翻转二叉树 剑指 Offer 27. 二叉树的镜像 116. 填充每个节点的下一个右侧节点指针 101. 对称二叉树 剑指 Offer 28. 对称的二叉树 114. 二叉树展开为链表 654. 最大二叉树 105. 从前序与中序遍历序列构造二叉树 剑指 Offer 07. 重建二叉树 652. 寻找重复的子树 剑指 Offer 26. 树的子结构 剑指 Offer 37. 序列化二叉树 二叉树层序遍历 剑指 Offer 32 - I. 从上到下打印二叉树 102. 二叉树的层序遍历 剑指 Offer 32 - II. 从上到下打印二叉树 II 二叉树的层序遍历非递归 二叉树的层序遍历递归 107. 二叉树的层次遍历 II 103. 二叉树的锯齿形层次遍历 剑指 Offer 32 - III. 从上到下打印二叉树 III 二叉搜索树 230
  • 【leetcode-Python】-BST-235. Lowest Common Ancestor of a Binary Search Tree
    题目链接 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ 描述 给定二叉搜索树BST,找出该树中两个指定节点的最近公共祖先。 最近公共祖先的定义为:”对于树T的两个节点p和q,最近公共祖先表示为一个节点x,满足x是p、q的祖先且x的深度尽可能大。(一个节点也可以是它自己的祖先)。 所有节点的值都唯一,p、q为不同节点且均存在于给定的BST中。 示例 输入:root = [6,2,8,0,4,7,9,null,null,3,5],p=2,q=8 输出:6 节点2和8的最近公共祖先是6。 解题思路 二叉搜索树又被称为二叉查找树、二叉排序树。二叉搜索树具备以下几个性质: (1) BST中每个节点如果存在左节点,左节点的值一定小于该节点的值。 (2) BST中每个节点如果存在右节点,右节点的值一定大于该节点的值。 (3)BST中任意一个非叶子节点的左子树中任意一个节点的值都小于当前节点值,右子树中任意一个节点的值都大于当前节点值。 (4)对BST进行中序遍历,可以得到一个升序序列。 找p和q的最近公共祖先时,我们要先把p和q给找到。因此我们仍采用递归的方式从上往下找,枚举所有可能: p和q在root的同一子树中: (1)如果p的节点值和q的节点值都小于root的节点值
  • 树的深度和高度之间有什么区别?(What is the difference between tree depth and height?)
    问题 这是算法理论中的一个简单问题。 它们之间的区别在于,在一种情况下,您要计算根节点和具体节点之间的最短路径上的节点数,而在其他边缘上则要数。 哪一个 回答1 我了解到深度和高度是节点的属性: 节点的深度是从节点到树的根节点的边数。 根节点的深度为0。 节点的高度是从节点到叶子的最长路径上的边数。 叶节点的高度为0。 一棵树的属性: 一棵树的高度将是其根节点的高度, 或等效地,其最深节点的深度。 树的直径(或宽度)是任意两个叶节点之间的最长路径上的节点的数目。 下面的树的直径为6个节点。 回答2 一棵树的高度和深度相等... 但是节点的高度和深度不相等,因为... 高度是通过从给定节点遍历到最深的叶子来计算的。 深度是从根到给定节点的遍历计算的..... 回答3 根据Cormen等。 算法简介(附录B.5.3)中,树T中节点X的深度定义为从T的根节点到X的简单路径的长度(边数)。节点Y的高度为从Y到叶子的最长向下简单路径上的边数。 一棵树的高度定义为其根节点的高度。 注意,简单路径是没有重复顶点的路径。 一棵树的高度等于树的最大深度。 节点的深度和节点的高度不一定相等。 参见第三版Cormen等的图B.6。 这些概念的说明。 有时我会遇到一些问题,要求人们计算节点(顶点)而不是边缘,因此请澄清一下,如果您不确定在考试或工作面试中应该计算节点或边缘。 回答4 我知道这很奇怪
  • 【数据结构】——各种树的定义
    1、二叉树 是树家族中中非常基础的数据结构 二叉树的定义:二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2i-1个结点;深度为k的二叉树至多有2k-1个结点;对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。 满二叉树和完全二叉树:   满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点。也可以这样理解,除叶子结点外的所有结点均有两个子结点。节点数达到最大值,所有叶子结点必须在同一层上。   满二叉树的性质:   1) 一颗树深度为h,最大层数为k,深度与最大层数相同,k=h;   2) 叶子数为2h;   3) 第k层的结点数是:2k-1;   4) 总结点数是:2k-1,且总节点数一定是奇数。   完全二叉树:若设二叉树的深度为h,除第 h 层外,其它各层 (1~(h-1)层) 的结点数都达到最大个数,第h层所有的结点都连续集中在最左边,这就是完全二叉树。   注:完全二叉树是效率很高的数据结构,堆是一种完全二叉树或者近似完全二叉树,所以效率极高,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化,二叉排序树的效率也要借助平衡性来提高,而平衡性基于完全二叉树。 2、平衡二叉树 平衡二叉树定义:平衡二叉树(Balanced Binary
  • 【数据结构X.3】先序遍历序列第k节点值,删去以x为根的子树,最近的公共祖先节点,非空二叉树的宽度,求解后序序列,叶子节点按从左到右的顺序连成一个单链表,递归非递归
    二叉树算法习题: 1.设计算法,求解先序遍历序列第k(1<=k<=n)个节点的值 int getKNodeVal(BiTree tr, int k) 2.对于树中每个元素为x的节点,删去以它为根的子树,释放相应的空间 BiTree DeleteValX(BiTree tr, char x) 3. p和q分别为指向二叉树中的任意两个节点的值,其中数值不会重复,找到离p和q最近的公共祖先节点 BiNode *FindAncestor(BiTree tr, char p, char q) 4.求非空二叉树b的宽度:具有节点数目最多的那一层的节点个数 int GetTreeWidth(BiTree tr) 5.假设一颗满二叉树,所有节点都不同,已知先序序列是pre,设计算法求解后序序列post void GetPostLine(int pre[], int h1, int t1, int post[], int h2, int t2) 6.1.非递归,设计算法将二叉树的叶子节点按从左到右的顺序连成一个单链表,表头指针为head,二叉树按照二叉链表方式存储,链接时,用叶节点的右指针域来存放单链表指针 BiTree TransToLinkList(BiTree tr) 7.第6题的递归算法:只有这样从下向上的计算,才能保证头指针是head,而且能正常访问子节点 BiNode *InOrder
  • 常见数据结构及面试常见代码题(1)
    数组 基本操作: 插入、删除、返回指定位置的元素、得到数组所有元素的数量。 面试常见问题: 1 寻找数组第k大的数字 2 找到数组中第一个不重复的整数 3 合并两个有序数组 4 重新排列数组中的正值和负值 栈 应用: 撤销操作 基本操作: Push 顶部插入 Pop 移除栈顶元素 isEmpty 栈为空则返回true Top 返回顶部元素,但不移除 面试常见问题: 5 用栈计算后缀表达式 6 对栈的元素进行排序 7 判断表达式是否括号平衡 队列 应用: 银行排队 基本操作: Enqueue(): 在队列尾部插入 Dequeue(): 移除队列头部 isEmpty(): 队列空则返回true Top: 返回队列第一个元素 面试常见问题: 8 用队列表示栈 9 对队列前k个元素倒序 10 使用队列生成1-n的二进制数 链表 是一种重要的线性数据结构,链表就像一个节点链,每个节点包含着自己的数据和指向后续节点的指针。链表包含一个头指针,指向链表的第一个元素。当链表为空时,他指向null或者无具体内容。 应用:实现文件系统,散列表或者邻接表 基本操作: InsertAtEnd: 在链表末尾插上元素 InsertAtHead:在链表开始插入指定元素 Delete:在链表中删除指定元素 DeleteAtHead:删除链接链表的第一个元素 Search:从链表中返回第一个元素 isEmpty
  • *236.二叉树最近公共祖先
    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4] 示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 示例 2: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。 说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 思路: 递归终止条件: 当越过叶节点,则直接返回 nullnull ;当
  • LeetCode刷题汇总
    LeetCode 1 两数之和 2 两数相加 3 无重复字符的最长子串 4 寻找两个正序数组的中位数 5 最长回文子串-动态规划 6 Z 字形变换 7 整数反转 8 字符串转换整数 (atoi) 9 回文数 10 正则表达式匹配 11 盛最多水的容器 12 整数转罗马数字 13 罗马数字转整数 14 最长公共前缀 15 三数之和 16 最接近的三数之和 17 电话号码的字母组合 18 四数之和 19 删除链表的倒数第N个节点 20 有效的括号 21 合并两个有序链表 22 括号生成 24 两两交换链表中的节点 25 K 个一组翻转链表 26 删除排序数组中的重复项 27 移除元素 28 实现 strStr() 29 两数相除 30 串联所有单词的子串 31 下一个排列 32 最长有效括号-动态规划 33 搜索旋转排序数组 34 在排序数组中查找元素的第一个和最后一个位置 35 搜索插入位置 36 有效的数独 37 解数独 38 外观数列 39 组合总和 40 组合总和 II 41 缺失的第一个正数 42 接雨水 43 字符串相乘 44 通配符匹配-动态规划 45 跳跃游戏 II 46 全排列 47 全排列 II 48 旋转图像 49 字母异位词分组 50 Pow(x, n) 51 N 皇后 52 N皇后 II 53 最大子序和 54 螺旋矩阵 55 跳跃游戏 56 合并区间 57