tree专题

树（Tree）——《啊哈！算法》

树什么是树？树是一种特殊的图，不包含回路的连通无向树。正因为树有着“不包含回路”这个特点，所以树就被赋予了很多特性。一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点，那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。一棵树有且只有一个根结点。没有父结点的结点称为根结点（祖先）。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶

226 Invert Binary Tree

//226 Invert Binary Tree//算法思路：主要使用递归算法public class Solution {public TreeNode invertTree(TreeNode root) {//1 出口空节点if (root==null)return null;//2 递归调用自己TreeNode left = root.left;TreeNode right = ro

Sorry！Hbase的LSM Tree就是可以为所欲为！

我们先抛出一个问题： LSM树是HBase里使用的非常有创意的一种数据结构。在有代表性的关系型数据库如MySQL、SQL Server、Oracle中，数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据库如HBase、Cassandra、LevelDB、RocksDB中，则是使用日志结构合并树（Log-structured Merge Tree，LSM Tr

【spring】does not have member field ‘com.sun.tools.javac.tree.JCTree qualid

spring-in-action-6-samples 的JDK版本最小是11，我使用了22： jdk21 jdk22 都与lombok 不兼容，必须使用兼容版本，否则报错： thingsboard 的大神解释了： java: java.lang.NoSuchFieldError: Class com

[LeetCode] 863. All Nodes Distance K in Binary Tree

题：https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/ 题目大意求给树中，距给定结点指定长度的所有结点的val 思路 tree -> graph 、 bfs 先遍历树，并用map记录每个结点的父结点，将树变为图，然后 bfs。 /*** Definition for a binary tree

js实现树级递归，通过js生成tree树形菜单(递归算法)

1、效果图需求：首先这是一个数据集—js的类型，我们需要把生成一个tree形式的对象 : var data = [{ id: 1, name: "办公管理", pid: 0 },{ id: 2, name: "请假申请", pid: 1 },{ id: 3, name: "出差申请", pid: 1 },{ id: 4, name: "请假记录", pid: 2 },{ id:

【unity实战】利用Root Motion+Blend Tree+Input System+Cinemachine制作一个简单的角色控制器

文章目录前言动画设置Blend Tree配置角色添加刚体和碰撞体代码控制人物移动那么我们接下来调整一下相机的视角效果参考完结前言 Input System知识参考：【推荐100个unity插件之18】Unity 新版输入系统Input System的使用，看这篇就够了 Cinemachine虚拟相机知识参考：【推荐100个unity插件之10】Unity最全的最详细的C

树链剖分 + 后缀数组 - E. Misha and LCP on Tree

E. Misha and LCP on Tree Problem's Link Mean: 给出一棵树，每个结点上有一个字母。每个询问给出两个路径，问这两个路径的串的最长公共前缀。 analyse: 做法：树链剖分+后缀数组. 记录每条链的串，正反都需要标记，组成一个长串. 然后记录每条链对应的串在大串中的位置,对大串求后缀数组,最后询问就是在一些链

数据结构 - Codeforces Round #353 (Div. 2) D. Tree Construction

Tree Construction Problem's Link ---------------------------------------------------------------------------- Mean: 给定n个数，按照构造Binary Search Tree的方式来构造BST树，按顺序输出每一个非root结点的父节点的值。 analyse

【HDU】4871 Shortest-path tree 最短路+点分治

传送门：【HDU】4871 Shortest-path tree 题目分析：学了点分治后来看这道题，简直就是水题。。。但是我竟然花了将近一个晚上才写出来。。。就因为一个地方写漏了T U T。。首先根据题意求一棵树，最短路一下，然后最小字典序就按照编号顺序遍历邻接表给节点标记。剩下的就是树分治的事了。在以重心X为根的子树中，按照X的子节点v的子树中最长路径包含节点数升序遍

【HDU】4812 D Tree 点分治

传送门：【HDU】4812 D Tree 题目分析：点分治搞之。乘积等于K的路径。首先我们定义一个path[ i ]用以记录从根结点x在子树x内的第 i 条路径的值（乘积）。然后每次我们搞完当前重心rt的一棵子树以后，我们用判断K*逆元[ path[ i ] * val[ rt ] %MOD ] % MOD 是否存在来确定乘积为K的路径是否存在，然后再用这个path[ i ]去更

【HDU】4670 Cube number on a tree 点分治

传送门：【HDU】4670 Cube number on a tree 题目分析：首先因为至多30个素数，3^30在long long以内，如果一条路径上的数的乘积是个立方数，则这条路径上每个素数因子的个数都应该是3的倍数，于是我们用三进制表示含有素数的状态，当且仅当状态为0（即所有素数的个数都是3的倍数）时这条路径上数的乘积为完全立方数。考虑树分治，每层分治，求出当前重心的一个儿子的一个

【codechef】 Prime Distance On Tree【求树上路经长度为i的路径条数】【点分治+FFT】

传送门：【codechef】 Prime Distance On Tree 点分治+FFT水题……竟然n*n爆int没发现…… 而且NTT TLE，FFT跑的超级快…… my code: my~~code: #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define clr( a , x ) m

【HDU】5436 Transmigration tree【树链剖分+dp+rmq】

题目链接：【HDU】5436 Transmigration tree #pragma comment(linker, "/STACK:16777216")#include <stdio.h>#include <string.h>#include <vector>#include <algorithm>using namespace std ;typedef long long LL ;

【HDU】5574 Colorful Tree【子树染色，询问子树颜色数——线段树+bit+lca+set】

题目链接：【HDU】5574 Colorful Tree 题目大意：对一个子树染色，询问一个子树的颜色数。题目分析： set set维护每种颜色所在的 dfs dfs序区间，修改均摊 nlogn nlogn。 #include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , i

zm-tree-org 数据量过大时，全部展开后，根节点点击收缩，树形消失

zm-tree-org 数据量过大时，全部展开后，根节点点击收缩，树形消失 <zm-tree-orgref="tree"@on-expand="onExpand"</zm-tree-org>export default {methods: {onExpand(e, data) {if (data.root === true && data.expa

java list转tree的工具类

今天帮前端做一个下拉框，关于行政区划的，表中是这种格式的，前端想要具有层次结构的tree类型，这里需要处理下，这里可以看出districtCode 和parentCode具有父子关系。这样就好处理一些。伪代码如下： import com.alibaba.fastjson.JSON;import com.alibaba.fastjson.JSONArray;import com.a

Segment Tree题型总结

Segment Tree 的基本操作 Segment Tree Build， Segment Tree Query， Segment Tree Modify 必须熟练掌握；线段树长什么样子，就是上面的样子，注意到数组A并不要求是sort的，range 是index的范围，每个leaf节点就是A中每个element. Interval Sum 思路：其实，这个题目是为了后面的follow

Maximum Depth of N-ary Tree

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]Output: 5 思路1：DFS ，divide and conquer /*// Definition for a Node.class Node {public int v

Cousins in binary tree

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4Output: true Input: root = [1,2,3,4], x = 4, y = 3Output: false 思路：就是level order traverse，BFS，记录一下parent, curNode, Depth; /*** Definition for

Average of Levels in Binary Tree

Input:3/ \9 20/ \15 7Output: [3, 14.5, 11]Explanation:The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11]. 思路：就是一个level order trav

N-ary Tree Level Order Traversal

Input: root = [1,null,3,2,4,null,5,6]Output: [[1],[3,2,4],[5,6]] 思路：就是一个queue的level order 收集； /*// Definition for a Node.class Node {public int val;public List<Node> children;public Node() {}pu

Closest Leaf in a Binary Tree

Input:root = [1,2,3,4,null,null,null,5,null,6], k = 2Diagram of binary tree:1/ \2 3/4/5/6Output: 3Explanation: The leaf node with value 3 (and not the leaf node with value 6) is nearest to the no

Binary Tree - Lowest Common Ancestor 题型总结

Lowest Common Ancestor of a Binary Search Tree 思路：这题跟 Lowest Common Ancestor of Binary Tree 一模一样。思路：就是找p的节点在不在左支，或者右支，找到各自左右节点，然后进行比较，如果两者不一样，说明当前的root就是lowest 父节点，如果左边为空，那就都在右边，返回右边的即可，如果右边为空，那就都在左

Tree的Traverse and divided conquer

Tree的traverse，Preorder, Inorder, Postorder ，这些都是用stack来模拟考察的比较多。参考这里： PreOrder, InOrder, PostOrder 题型总结这里主要总结，divide and conquer 逻辑，往上返回result的情况； Lowest Common Ancestor of a Binary Search Tree 思路

echart自适应tree树图，结构组织图模板

处理数据(代码中有处理数据逻辑，可忽略，因为后端返回的格式不匹配，需要自己处理) [{ name: ‘test1’, children: [{ name: ‘test2’ }] }] <template><div class="boxEchart"><div ref="echart" :style="{ width: width, height: height }"></div></div><