方法一:递归算法,解决一层地问题。递归下去 1,判断根节点是否为null , 是,就返回 0; 2,非null 的话,就返回对左右子树的递归判断。树的最大深度等于“左子树和右子树的最大深度的最大值” + 当前的深度 1. 方法二: 使用BFS宽度优先搜索遍历整个树,在遍历过程中,记录数的深度。 1,建立一个queue , 保存...
树上问题若干 树上差分 即在树上进行差分。 例题 1 (点差分) P3128 [USACO15DEC] Max Flow P 题意:对树上一条路径 + 1,求最大点权值。 做法 设操作 s -> t 路径,则设差分数组 \(d\), 操作为 d[s]++,d[t]++,d[lca(s,t)]-
funcinorderTraversal(root*TreeNode)[]int{varres[]intstack:=[]*TreeNode{}now:=rootfornow!=nil||len(stack)!=0{fornow!=nil{stack=append(stack,now)now=now.Left}now=stack[len(stack)-1]stack=stack[:len(stack)-1]res=append(res,now.Val)now=now.Right}returnres} 2.二叉树的前序遍历 递...
1.求树的高(深)度问题 Leetcode 上面关于这方面的题目如下:104. 二叉树的最大深度559. N 叉树的最大深度111. 二叉树的最小深度110. 平衡二叉树1.1 二叉树的(最大)高度根据定义,二叉树的最大高度递推公式为: max…
处理重复数字的技巧就是将数字: a[i]=a[i]<<20+i 然后放到平衡树里,接着取出其实际值的时候只需计算 x>>20 的结果。 代码为,code: #include <bits/stdc++.h> #include <bits/extc++.h> // #define int long long using namespace std; using namespace __gnu_pbds; using Tree = tree<int64_...
输入:一棵树 输出:这棵树中包含所有最深节点的最小子树的根节点(简称包最小) 简单粗暴的方法才是好方法——鲁迅 于是递归函数就这样写: funsubtreeWithAllDeepest(root:TreeNode?):TreeNode? 但是转念一想,如果一个节点有 left 和 right ,并调用这个递归函数得到 left 和 right 的递归结果,怎么比较两个结果哪...
B树,又称多路平衡查找树,B树中所有结点的孩子结点数的最大值称为B树的阶。 一颗m阶B树或是空树,或是满足如下特性的m叉树: 1)树中每个结点至多有m棵子树、m-1个关键字。 根节点不是终端节点(非叶子节点),则至少有两棵子树、1个关键字(由 1)得到:2阶-1=1个关键字)。
构建FP树,根节点为null,然后按频率排序后的项目列表为a, b, c。 遍历事务,构建FP树。 挖掘FP树,得到频繁项集:{a:4}, {b:4}, {c:3}, {a,b:3}, {a,c:2}, {b,c:2}, {a,b,c:2}。 例题2 数据集: 事务ID 项目列表 001 面包, 牛奶 002 面包, 尿布, 啤酒 003 牛奶, 尿布, 啤酒, ...
《数据结构与算法设计》树-习题 树的练习题 1.具有n个顶点的二叉树，共有多少边？n-1 2、若一个具有N个顶点，K条边的无向图是一个森林(N>K)，那么该森林有多少棵树？N－K 3、已知一棵度为m的树中有N1个度为1的节点，N2个度为2的节点，…，Nm个度为m的节点。问该树有多少叶子节点？N0=N2+2N3...
一套模板搞定二叉树算法题--二叉树算法讲解003,1、二叉树自顶向下(top-down)递归1.1、leetcode104题目和题意:图示:题解:1.2、自顶向下特点1.3、leetcode226题目和题意:题解: