树形结构

树形构造先序遍历树实际公司我的项目中常常应用到树形构造性能,如机械部件的保护等,当数据量达到肯定级别会有性能问题: 查问效率低,无论是在数据库中做递归还是在代码中递归都会节约计算性能如果一次性查给前台,数据量大的状况话下浏览器会卡顿当查问退出其余业务逻辑的时候会导致代码复杂度减少Modified Preorder Tree Traversal (改良先序遍历树）网上查找计划的时候看到这种解决方案, 该计划能够疾速查找子孙节点。 原理设节点有left,right, parentId三个字段,根节点left=1, right=2;节点插入子节点的时候, 令新节点的left=parent.right,right=left+1;找出所有节点满足left,right大于新增点的left,right, 另这些节点的left和right值加2;如此咱们能失去相似上面的构造 跟二叉树的先序遍历很像 如此，当咱们须要查问江苏上面所有的子孙节点的时候, 能够用以下sql去查问SELECT * FROM table_name where lft > 2 and rgt < 11; 插入删除节点这种构造对于增删操作效率较低, 须要更改大量节点的左右值, 能够写成存储过程 插入: 节点插入子节点的时候, 令新节点的left=parent.right,right=left+1;删除: 每删一个节点, 相当于缩小了right-left+1个子节点, 对于parent.right>left和parent.left >left的状况, 减去delta即可实现表构造CREATE TABLE `nested_category` ( `category_id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(255) CHARACTER SET utf8mb4 NOT NULL, `parent_id` int(255) NOT NULL DEFAULT '0', `lft` int(255) NOT NULL, `rgt` int(255) NOT NULL, `deleted` tinyint(255) NOT NULL DEFAULT '0', PRIMARY KEY (`category_id`)) ENGINE=InnoDB AUTO_INCREMENT=19 DEFAULT CHARSET=latin1插入存储过程CREATE DEFINER=`root`@`%` PROCEDURE `insert_node_into_nested_category`(IN `nodeId` int,IN `namee` varchar(255))BEGIN #Routine body goes here... DECLARE lftt int(255); DECLARE rgtt int(255); DECLARE parentId int; SELECT category_id, rgt, rgt+1 INTO parentId, lftt, rgtt FROM nested_category WHERE category_id = nodeId; # SELECT parentId,lftt,rgtt,nodeId,namee; UPDATE nested_category SET lft=lft+2 WHERE lft > lftt; UPDATE nested_category SET rgt=rgt+2 WHERE rgt >= lftt; INSERT into nested_category (name,lft,rgt,parent_id) VALUES (namee,lftt,rgtt,parentId);END删除存储过程CREATE DEFINER=`root`@`%` PROCEDURE `del_node_from_nested_category`(IN `nodeId` int)BEGIN #Routine body goes here... DECLARE lftt,rgtt,delta int; SELECT lft, rgt, rgt-lft+1 INTO lftt, rgtt, delta FROM nested_category WHERE category_id=nodeId; # select lftt,rgtt,delta; UPDATE nested_category SET lft=lft-delta where lft > rgtt; UPDATE nested_category set rgt=rgt-delta WHERE rgt > rgtt; DELETE from nested_category WHERE category_id=nodeId or parent_id=nodeId;END测试 ...

奢侈并查集 // 每个点的父亲节点int p[N];// 每个汇合的大小int sz[N];void init(int n) { for (int i = 1; i <= n; i ++ ) { p[i] = i; sz[i] = 1; }}int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x];}void merge(int x, int y) { x = find(x), y = find(y); p[x] = y; sz[y] += sz[x];}带门路压缩的并查集 // 每个点的父亲节点int p[N];// 每个点间隔根节点的间隔int dist[N];// 每个汇合的大小int sz[N];void init(int n) { for (int i = 1; i <= n; i ++ ) { p[i] = i; dist[i] = 0; sz[i] = 1; }}int find(int x) { if (p[x] == x) return x; int root = find(p[x]); d[x] += d[p[x]]; return p[x] = root;}void merge(int x, int y) { x = find(x), y = find(y); p[x] = y; d[x] = sz[y]; sz[y] += sz[x];}

过滤/筛选树节点又是树，是我跟树杠上了吗？—— 不，是树的问题太多了！ 相干文章举荐： 应用递归遍历并转换树形数据（以 TypeScript 为例）从列表生成树 (JavaScript/TypeScript) 过滤和筛选是一个意思，都是 filter。 对于列表来说，过滤就是丢掉不须要的，留下须要的。但对于树来说就得分状况了。 如果想“过滤掉”（丢掉）某些节点，会把它的子节点一并摈弃，就像砍树枝一样，干之不存，枝将焉附？这种状况多是去除不须要的子树。如果是想“查找”某些节点，会将找到的节点及其上溯到根的所有节点都保留下来。对于找到的节点，除了保留其残缺门路之外，对其子树还有两种解决形式： 一种是“到此为止”，也就是说，如果其子树中没有符合条件的节点，那就不须要了，砍掉。须要定位到符合条件的节点以便后继操作是采纳这种形式，这也是最罕用的查找形式。另一种是保留其残缺子树。如果须要应用符合条件节点的子节点（比方抉择指定部门及其子部门）会采纳这种形式。过滤和查找的次要区别在于：“过滤”通常会遇到不合乎保留条件（或合乎剔除条件）的节点就间接砍掉，不论其子树中是否还存在合乎保留条件的节点；而查找则会始终找到叶节点上，只有整条门路都没有合乎保留条件的节点，才会从其某个先人节点上砍掉（先人节点是否保留取决于其下是否存在合乎保留条件的子孙节点）。 上面一样一样来。示例代码应用 TypeScript 编写，示例数据起源于从列表生成树 (JavaScript/TypeScript) 一文，同时应用该文中定义的节点类型接口： interface TreeNode { id: number; parentId: number; label: string; children?: TreeNode[]}过滤掉不须要的节点过滤掉不须要的节点，思路比较简单： 遍历以后节点的所有子节点，须要的留，不须要的删对留下的节点，通过递归进行过滤按此思路，TypeScript 代码是 /** * @param nodes 要过滤的树节点集（多根） * @param predicate 过滤条件，返回 `true` 保留 * @returns 过滤后的树节点集 */function filterTree( nodes: TreeNode[] | undefined, predicate: (node: TreeNode) => boolean): TreeNode[] | undefined { if (!nodes?.length) { return nodes; } // 间接应用 Array 的 filter 能够过滤当层节点 return nodes.filter(it => { // 不符合条件的间接砍掉 if (!predicate(it)) { return false; } // 符合条件的保留，并且须要递归解决其子节点 it.children = filterTree(it.children, predicate); return true; });}如果对示例数据（见前文）进行过滤，仅保留 id 是偶数的节点，那后果是 ...

什么是差分？定义：差分就是数组中每一项都与前一项做差，最初得出的序列。例如：数组：2,5,3,7,2,3差分后的序列：2,3,-2,4,-5,1,-3留神：第一个数与原数组雷同，相当于2-0；最初一个数与原数组互为相反数，相当于0-3；差分的性质：1.差分序列的前缀和就是原数组；2.将原数组在[L,R]区间上的数全副加1，相当于让差分数组在L处+1，在R+1处-1； 树上差分思考差分的一个利用：图片起源：https://blog.csdn.net/a135193... 树上差分的两种思路：1.找被所有门路独特笼罩的边。例题：洛谷：https://www.luogu.com.cn/prob...剖析见代码： //1.找被所有门路独特笼罩的边。#include <algorithm>#include <iostream>#include <stdio.h>#include <cstring>#include <vector>using namespace std;const int N = 300010;int fa[N][26];int depth[N], dist[N];int tmp[N], pre[N];int cnt,flag;//tmp存节点呈现的次数，即节点与节点父亲的边在所有门路中呈现的次数//pre存节点与节点父亲之间的边，本题中存的是边权，别的题中也有可能存编号int n, m;struct node{ int s, t; int lca;} path[N];int head[N], nex[2 * N], val[2 * N], to[2 * N], idx;int u, v, w;void add(int u, int v, int w){ to[idx] = v; val[idx] = w; nex[idx] = head[u]; head[u] = idx++;}int que[N];void bfs(int root){ memset(depth, 0x3f, sizeof(depth)); depth[0]=0; depth[root] = 1; int h = 0, t = 0; que[t++] = root; while (h != t) { int top = que[h++]; for (int i = head[top]; ~i; i = nex[i]) { int j = to[i]; int w = val[i]; if (depth[j] > depth[top] + 1) { depth[j] = depth[top] + 1; dist[j] = dist[top] + val[i]; que[t++] = j; pre[j] = val[i]; fa[j][0] = top; for (int k = 1; k <=21; k ++) { fa[j][k] = fa[fa[j][k - 1]][k - 1]; } } } }}int get_lca(int u, int v){ if (depth[u] < depth[v]) { swap(u, v); } //第一步：先让u跳到与v同一高度 for (int i = 21; i >= 0; i--) { if (depth[fa[u][i]] >= depth[v]) { u = fa[u][i]; } } if (u == v) //非凡状况，u和v调到同一高度之后重合，只需返回u或v即可 { return u; } //第二步，让u和v跳到最近公共先人的下一层 for (int i = 21; i >= 0; i--) { if (fa[u][i] != fa[v][i]) { u = fa[u][i]; v = fa[v][i]; } } return fa[u][0]; //再向上跳一步就是root}int judge(int a,int f,int cnt,int maxn){ for(int i=head[a];~i;i=nex[i]) { int j=to[i]; if(j==f) { continue; } tmp[a]+=judge(j,a,cnt,maxn); } if(tmp[a]==cnt&&pre[a]>=maxn) { flag=1; } return tmp[a];}bool check(int x){ memset(tmp, 0, sizeof(tmp)); cnt = 0,flag=0; int maxn = 0; for (int i = 1; i <= m; i++) { int dis = dist[path[i].s] + dist[path[i].t] - 2 * dist[path[i].lca]; if (dis > x) { cnt++; maxn = max(maxn, dis - x); //s,t加一，最近公共先人-2 tmp[path[i].s]++; tmp[path[i].t]++; tmp[path[i].lca] -= 2; } } if (!cnt) { return true; } judge(1,0,cnt,maxn); if(flag) { return true; } return false;}int main(){ scanf("%d %d", &n, &m); memset(head, -1, sizeof(head)); for (int i = 0; i < n - 1; i++) { scanf("%d %d %d", &u, &v, &w); add(u, v, w); add(v, u, w); } bfs(1); for (int i = 1; i <= m; i++) { scanf("%d %d", &path[i].s, &path[i].t); path[i].lca = get_lca(path[i].s, path[i].t); } //二分找正确答案 long long int l = 0, r = 3000000000; while (l < r) { int mid = (l + r) / 2; if (check(mid)) { r = mid; } else { l = mid + 1; } } cout << l << endl; return 0;}

少数状况下，从服务端拿到用于树形显示的数据，自身是立体的，也就是列表。这是因为关系型数据库是以“行”为单位保留数据，所以它保留了每一个节点的数据，而这个数据中蕴含了它与父节点之间的分割（比方 parentId）。 前端要以树形显示这样的列表数据，须要把列表数据转换成树形构造数据。这个的树形构造是指：每个节点数据中都含有其子节点集（通常是 children 属性）。所以树形结节的数据结构次要须要蕴含如下信息（TypeScript 数据结构申明）： interface TreeNodeBase<TKey extends string | number = number> { id: TKey; parentId: TKey children?: TreeNodeBase<TKey>[]}这里应用了 TypeScript 的泛型语法来形容树节点构造。从天然语义不难明确： 树节点的 id（包含 parentId）是 string 或者 number 类型，较为少见的状况下也可能是混合类型。树节点蕴含一个 parentId，因为这个 parentId 不是可选的（没用 ? 号申明），所以根节点通常会用一个非凡值，或者不应该存在的 ID 值，比方 0（如果是数据库自增字段，个别会从 1 开始）树节点蕴含一个可选的子节点集 children，其每个元素了以后元素是雷同的类型定义 TKey 这个类型参数的作用就是为了束缚子节点类型必须和父节点统一，防止父节点的 id 是 string 类型，子节点的 id 却搞成了 string 这种状况（混合类型 id 的状况不含在内）科普完树节点的数据结构，再来说转换过程。一般来说可能会在三个阶段进行转换： 后端送进去之前先解决好前端拿到之后本人转换，再用转换后数组去渲染页面前端应用的 UI 组件自带转换性能，不须要开发者去操心（比方 zTree）这里就以 JS/TS 为例来说说如何进行转换。语言不重要，重要的是该如何来思考，以及应用什么办法进行转换。这里同时应用 JS 和 TS 的起因在于：带相似的 TS 能够清晰地形容数据结构，而 JS 代码可能少数人看起来更没有压力。 一、筹备示例数据（随机产生）以列表示意的树形数据，其每一条（行）肯定须要分明的形容这个节点的三个因素： 本身标识（ID），通常用 id、key、name 等属性名，它能惟一标识一个节点与父节点的关系，通过应用 parentId、upstreamId 等名称，分明的指明其父节点节点本人携带的数据，比方显示的文本，title、label 等，和一些其余数据。为了疾速筹备示例数据，咱们应用一个最简略，属性意义也十分明确的数据结构。留神，这个构造是与数据表相匹配的立体构造，不含 children 子集。 ...

提出问题：给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。 解决思路：使用新的遍历方式（右子树，根、左子树）遍历整棵树。设置全局变量累加值，再逐一更新节点。 代码如下(￣▽￣)： # Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def __init__(self): self.re = 0 def convertBST(self, root: TreeNode) -> TreeNode: if root==None: return root self.toBST(root) return root def toBST(self,node: TreeNode): if node==None: return else: self.toBST(node.right) node.val=node.val + self.re self.re = node.val self.toBST(node.left)时间与空间复杂度： 链接：https://leetcode-cn.com/probl...

1. 前言想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手。非线性表（树、堆），可以说是前端程序员的内功，要知其然，知其所以然。 笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。 非线性表中的树、堆是干嘛用的 ？其数据结构是怎样的 ？ 希望大家带着这两个问题阅读下文。 2. 树 树的数据结构就像我们生活中的真实的树，只不过是倒过来的形状。 术语定义 节点：树中的每个元素称为节点，如 A、B、C、D、E、F、G、H、I、J。父节点：指向子节点的节点，如 A。子节点：被父节点指向的节点，如 A 的孩子 B、C、D。父子关系：相邻两节点的连线，称为父子关系，如 A 与 B，C 与 H，D 与 J。根节点：没有父节点的节点，如 A。叶子节点：没有子节点的节点，如 E、F、G、H、I、J。兄弟节点：具有相同父节点的多个节点称为兄弟节点，如 B、C、D。节点的高度：节点到叶子节点的最长路径所包含的边数。节点的深度：根节点到节点的路径所包含的边数。节点层数：节点的深度 +1（根节点的层数是 1 ）。树的高度：等于根节点的高度。森林： n 棵互不相交的树的集合。 高度是从下往上度量，比如一个人的身高 180cm ，起点就是从 0 开始的。深度是从上往下度量，比如泳池的深度 180cm ，起点也是从 0 开始的。高度和深度是带有度字的，都是从 0 开始计数的。而层数的计算，是和我们平时的楼层的计算是一样的，最底下那层是第 1 层，是从 1 开始计数的，所以根节点位于第 1 层，其他子节点依次加 1。 二叉树分类 二叉树每个节点最多只有 2 个子节点的树，这两个节点分别是左子节点和右子节点。如上图中的 1、 2、3。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。以此类推，自己想四叉树、八叉树的结构图。 满二叉树一种特殊的二叉树，除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树。如上图中的 2。完全二叉树一种特殊的二叉树，叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。如上图的 3。完全二叉树与不是完全二叉树的区分比较难，所以对比下图看看。 堆之前的文章 栈内存与堆内存 、浅拷贝与深拷贝 中有说到：JavaScript 中的引用类型（如对象、数组、函数等）是保存在堆内存中的对象，值大小不固定，栈内存中存放的该对象的访问地址指向堆内存中的对象，JavaScript 不允许直接访问堆内存中的位置，因此操作对象时，实际操作对象的引用。 ...

十多年来，NAS中已经存在的目录和文件达到10亿之多，在设计和开发备份系统的过程中碰到了很多挑战，本文将分享大量文件名记录的树形结构存储实践。 一、引言既然是定期备份，肯定会有1次以上的备份。对于一个特定目录，每次备份时都要与上次备份时进行比较，以期找出哪些文件被删除了，又新增了哪些文件，这就需要每次备份时把该目录下的所有文件名进行保存。我们首先想到的是把所有文件名用特定字符进行拼接后保存。由于我们使用了MySQL保存这些信息，当目录下文件很多时，这种拼接的方式很可能超出MySQL的Blob长度限制。根据经验，当一个目录有大量文件时，这些文件的名称往往是程序生成的，有一定规律的，而且开头一般是重复的，于是我们想到了使用一种树形结构来进行存储。 例如，一个有abc、abc1、ad、cde 4个文件的目录对应的树如图1所示。 图1 树形结构示例 图1中，R表示根节点，青色节点我们称为结束节点，从R到每个结束节点的路径都表示一个文件名。可以在树中查找是否含有某个文件名、遍历树中所有的文件名、对树序列化进行保存、由序列化结果反序列化重新生成树。 二、涉及的数据结构注意：我们使用java编写，文中涉及语言特性相关的知识点都是指java。 2.1 Node的结构包括根节点在内的每个节点都使用Node类来表示。代码如下： class Node { private char value; private Node[]children = new Node[0]; private byte end = 0; }字段说明： value：该节点表示的字符，当Node表示根节点时，value无值。children：该节点的所有子节点，初始化为长度为0的数组。end：标记节点是否是结束节点。0不是；1是。叶子节点肯定是结束节点。默认非结束节点。2.2 Node的操作 public Node(char v); public Node findChild(char v); public Node addChild(char v);操作说明： Node：构造方法。将参数v赋值给this.value。findChild：查找children中是否含有value为v的子节点。有则返回子节点，没有则返回null。addChild：首先查找children中是否已经含有value为v的子节点，如果有则直接将查到的子节点返回；否则创建value为v的节点，将children的长度延长1，将新创建的节点作为children的最后一个元素，并返回新创建的节点。2.3 Tree的结构 class Tree { public Node root = new Node(); }字段说明：Tree只含有root Node。如前所述，root的value无值，end为0。初始时的children长度为0。 2.4 Tree的操作 public void addName(String name) ; public boolean contain(String name); public Found next(Found found); public void writeTo(OutputStream out); public static Tree readFrom(InputStream in);操作说明： ...

前沿    前端中设计数据结构的方面不多，最常用的就是对树结构的一些操作。从某种意义上来说，前端工作本身就是和树结构打交道的一个工作方向。毕竟，DOM就是天然的树结构。所以如何能够良好地对树结构进行操作，是前端工程师不可或缺的一项能力。 树结构定义    什么是树结构呢？从数据结构的角度来讲： 树是非线性数据结构每个节点可能会有0个或多个后代每个节点具备唯一的父节点（如果有多个父节点，那就是图了）分类树根据节点的不同可以分为不同的类型，最常见的分类是： 二叉树二叉搜索树平衡二叉查找树红黑树具体他们之间的区别这里就不细说了，具体请查看详情 前端中常见的树结构DOM树结构下面的html结构就是一个天然的树结构。每个Dom节点下面，有0/1/多个子节点。 对象树结构数组形式特点: 每一个对象节点，下面可能会有children，也可能没有childrenlet obj = [ { id: 1, type: 'dom', children: [ { id: 2, type: 'html' } ] }, { id: 3, type: 'css', children: [ { id: 4, type: 'javascript' } ] }];对象形式最常见的就是抽象语法树： 特点: 对象的属性下面有不同的属性，每一个属性下面可能还会有不同的属性这种格式经常在数据统计中出现。 Javascript中树结构的遍历    其实在我看来，树的结构形式有很多种，但是，前端工作中很少涉及对树节点的修改等操作，大部分是遍历和统计数据。 需求场景：下面以Dom树结构为例： 1、需要输出每个节点的名称和节点深度 3、深度优先和广度优先都需要实现假定已经有了对应的树结构，子节点是childNodes（为啥不用children呢？自己去查吧）深度优先遍历深度优先遍历，又叫DFS（deep first search），遍历顺序是优先遍历节点的子节点，然后再是节点的兄弟节点。 递归输出function DeepSearch(node, deep = 0) { const child = node.childNodes; const { nodeName } = node; console.log(`name:${nodeName},deep:${deep}`); for(let i = 0, len = child.length; i < len; i++) { DeepSearch(child[i], deep + 1); }}非递归输出function deepSearch(node, deep = 0) { const stack = []; const deepArr = []; stack.push(node); deepArr.push(0); while(stack.length !== 0){ const node = stack.shift(); const deep = deepArr.shift(); const { nodeName } = node; console.log(`name:${nodeName},deep:${deep}`); const nodes = child.childNodes; for( let i = node.length; i > 0; i--) { stack.unshift(nodes[i]); deep.unshift(deep + 1); } }}广度优先遍历广度优先，正好和深度优先策略相反，先遍历节点的兄弟节点，再遍历子节点。 ...

题目You need to find the largest value in each row of a binary tree.Example:Input: 1 / \ 3 2 / \ \ 5 3 9 Output: [1, 3, 9]讲解又是树的层次遍历题。相同的题我已经做了两个了：637. Average of Levels in Binary Tree、429. N-ary Tree Level Order TraversalJava代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { List<Integer> result = new ArrayList<>(); public List<Integer> largestValues(TreeNode root) { if(root==null){ return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int count = 1; while(!queue.isEmpty()){ List<Integer> list = new ArrayList<>(); int floorSize = 0; for(int i=0;i<count;i++){ TreeNode now = queue.poll(); list.add(now.val); if(now.left!=null){ queue.offer(now.left); floorSize++; } if(now.right!=null){ queue.offer(now.right); floorSize++; } } int max = list.get(0); for(Integer x:list){ if(max<x){ max = x; } } count = floorSize; result.add(max); } return result; }} ...

题目Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.Example 1: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].Note:The range of node’s value is in the range of 32-bit signed integer.讲解这题跟429. N-ary Tree Level Order Traversal很像。都是广度优先遍历树（也就是按层级遍历树）。java代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { List<Double> result = new ArrayList<>(); public List<Double> averageOfLevels(TreeNode root) { if(root==null){ return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int children_num=1; while(!queue.isEmpty()){ double sum = 0; int count=0; for(int i=0;i<children_num;i++){ TreeNode now = queue.poll(); sum += now.val; if(now.left!=null){ count++; queue.offer(now.left); } if(now.right!=null){ count++; queue.offer(now.right); } } sum /= children_num; result.add(sum); children_num = count; } return result; }} ...

题目Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).For example, given a 3-ary tree:We should return its level order traversal:[ [1], [3,2,4], [5,6]]Note:The depth of the tree is at most 1000.The total number of nodes is at most 5000.[题目地址]https://leetcode.com/problems…讲解这道题我真的想了有很久，刚开始想用队列，但是发现不知道怎么分割每一层，于是就想还是用递归。后来越发想不明白，最后看了别人的解法。其实分割每一层是可以做到的。以后要多练习。java代码/// Definition for a Node.class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; }};/class Solution { List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<List<Integer>> levelOrder(Node root) { if(root==null){ return result; } Queue<Node> queue = new LinkedList<>(); queue.offer(root); int children_num = 1; List<Integer> rootList = new ArrayList<Integer>(); rootList.add(root.val); result.add(rootList); while(!queue.isEmpty()){ List<Integer> list = new ArrayList<>(); int count=0; for(int i=0;i<children_num;i++){ Node now = queue.poll(); if(now.children!=null){ for(Node node:now.children){ queue.offer(node); list.add(node.val); count++; } } } children_num = count; if(list.size()>0){ result.add(list); } } return result; }} ...

题目Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.Example 1:Input: 1 / \ 0 2 L = 1 R = 2Output: 1 \ 2Example 2:Input: 3 / \ 0 4 \ 2 / 1 L = 1 R = 3Output: 3 / 2 / 1题目地址讲解这道题对锻炼递归能力很有帮助。思路如下：如果当前节点大于R或小于L，肯定是要抛弃的。如果大于R，就返回其左子树（要对左子树继续裁剪），如果小于L，就返回其右子树（要对右子树继续裁剪）。如果在L和R之间，就继续遍历其左右进行裁剪。Java代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode trimBST(TreeNode root, int L, int R) { if(root==null){ return root; } if(root.val<L){ return trimBST(root.right, L, R); }else if(root.val>R){ return trimBST(root.left, L, R); }else{ root.left = trimBST(root.left, L, R); root.right = trimBST(root.right, L, R); } return root; }} ...

题目Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.Example 1:Input: [5,3,6,2,4,null,8,1,null,null,null,7,9] 5 / \ 3 6 / \ \ 2 4 8 / / \ 1 7 9Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 Note:The number of nodes in the given tree will be between 1 and 100.Each node will have a unique integer value from 0 to 1000.题目地址讲解这道题讲道理本来应该是很简单的，但我犯了一个很愚蠢的错误，就是直接使用原来的树的结点，这样原来的树的结构也被带过来了，导致形成了死递归。其实我只需要原来的结点的值。temp.right = new TreeNode(root.val);而不是：temp.right = root;Java代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { TreeNode result = new TreeNode(0); TreeNode temp = result; public TreeNode increasingBST(TreeNode root) { if(root==null){ return root; } if(root.left!=null){ increasingBST(root.left); } temp.right = new TreeNode(root.val); temp = temp.right; if(root.right!=null){ increasingBST(root.right); } return result.right; }} ...

题目Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).Two binary trees are considered leaf-similar if their leaf value sequence is the same.Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.Note:Both of the given trees will have between 1 and 100 nodes.讲解这道题的思路很简单，先扫描出两个树的叶子结果集，然后比较就行了。考察点是树的遍历。递归的时候首先要判断结点是否为空。Java代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public boolean leafSimilar(TreeNode root1, TreeNode root2) { List<Integer> leaves1 = new ArrayList<>(); List<Integer> leaves2 = new ArrayList<>(); getLeaves(root1, leaves1); getLeaves(root2, leaves2); if(leaves1.size()!=leaves2.size()){ return false; }else{ for(int i=0;i<leaves1.size();i++){ if(leaves1.get(i)!=leaves2.get(i)){ return false; } } } return true; } private void getLeaves(TreeNode root, List<Integer> leaves){ if(root==null){ return; } if(root.left==null && root.right==null){ leaves.add(root.val); return; } getLeaves(root.left, leaves); getLeaves(root.right, leaves); }} ...

题目Given a n-ary tree, find its maximum depth.The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.For example, given a 3-ary tree:We should return its max depth, which is 3.Note:The depth of the tree is at most 1000.The total number of nodes is at most 5000.题目地址讲解这道题需要对每次层的深度做个记录，我直接使用结点的val属性来记录深度。另外就是给根节点深度置为1的时候有个技巧，设置一个一次性的flag。Java代码/// Definition for a Node.class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; }};/class Solution { private int result=0; private boolean flag = true; public int maxDepth(Node root) { if(root==null){ return result; } if(flag){ root.val=1; flag = false; } if(result<root.val){ result = root.val; } for(Node node:root.children){ node.val = root.val+1; maxDepth(node); } return result; } } ...

题目Given an n-ary tree, return the postorder traversal of its nodes’ values.For example, given a 3-ary tree:Return its postorder traversal as: [5,6,3,2,4,1].Note:Recursive solution is trivial, could you do it iteratively?题目地址讲解这道题跟先序遍历差不多，调换一下添加结点的顺序而已。参考：leetcode讲解–589. N-ary Tree Preorder Traversal但这道题的迭代解法稍微有点麻烦，需要一个标记，初次访问一个结点的时候我们并不能立即将它的值加进结果里，而是要等它的所有孩子访问完毕再加。也就是说我们第一次访问它并不pop，第二次访问它才pop。Java代码递归解法：/// Definition for a Node.class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; }};/class Solution { private List<Integer> result = new ArrayList<>(); public List<Integer> postorder(Node root) { if(root==null){ return result; } for(Node node:root.children){ postorder(node); } result.add(root.val); return result; }}迭代解法：/// Definition for a Node.class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; }};/class Solution { private List<Integer> result = new ArrayList<>(); private Stack<Bundle> stack = new Stack<>(); private Stack<Bundle> stack_temp = new Stack(); public List<Integer> postorder(Node root) { if(root==null){ return result; } Bundle rootBundle = new Bundle(root); stack.push(rootBundle); while(!stack.empty()){ Bundle bundle = stack.peek(); if(bundle.flag){ result.add(stack.pop().node.val); continue; } for(Node node:bundle.node.children){ Bundle d = new Bundle(node); stack_temp.push(d); } while(!stack_temp.empty()){ stack.push(stack_temp.pop()); } bundle.flag = true; } return result; } class Bundle{ Node node; Boolean flag; public Bundle(Node node){ flag = false; this.node = node; } }} ...

题目Given an n-ary tree, return the preorder traversal of its nodes’ values.For example, given a 3-ary tree:Return its preorder traversal as: [1,3,5,6,2,4].Note:Recursive solution is trivial, could you do it iteratively?题目地址讲解如果用递归来解题的话，还是非常简单的。如果要用迭代来解题，无非就是用栈来实现。要注意的一点是，需要一个额外的栈来把压栈的顺序倒一下序。Java代码递归代码：/// Definition for a Node.class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; }};/class Solution { private List<Integer> result = new ArrayList<>(); public List<Integer> preorder(Node root) { if(root==null){ return result; } result.add(root.val); for(Node node:root.children){ preorder(node); } return result; }}迭代代码：/// Definition for a Node.class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; }};/class Solution { private List<Integer> result = new ArrayList<>(); private Stack<Node> stack = new Stack<>(); private Stack<Node> stack_temp = new Stack(); public List<Integer> preorder(Node root) { if(root==null){ return result; } stack.push(root); while(!stack.empty()){ Node theNode = stack.pop(); result.add(theNode.val); for(Node node:theNode.children){ stack_temp.push(node); } while(!stack_temp.empty()){ stack.push(stack_temp.pop()); } } return result; }} ...