# 力扣 1519——子树中标签相同的节点数

## 原题

```输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"

```

```输入：n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"

```

```输入：n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"

```

```输入：n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa"

```

```输入：n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"

```

• 1 <= n <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• labels.length == n
• labels 仅由小写英文字母组成

## 解题

### 首次尝试

```class Solution {

public int[] countSubTrees(int n, int[][] edges, String labels) {
// 构造树
for (int[] edge : edges) {
// edge[0]的子节点
if (child == null) {
tree[edge[0]] = child;
}
// 增加子节点
}

// 结果
int[] result = new int[n];
// 遍历并计算
for (int i = 0; i < n; i++) {
// 需要遍历的字符
char cur = labels.charAt(i);
// 该节点的子树中与该字符相同的节点数
int curCount = 0;
// 广度优先遍历
while(!searchList.isEmpty()) {
int index = searchList.removeFirst();
if (cur == labels.charAt(index)) {
curCount++;
}
// 找出该节点的子树
if (tree[index] == null) {
continue;
}
}

result[i] = curCount;
}

return result;
}
}
```

```输入：
4
[[0,2],[0,3],[1,2]]
"aeed"

[1,2,1,1]

[1,1,2,1]
```

```1   0
\ / \
2   3
```

```    0
/ \
2   3
/
1
```

### 双向记录构造树

```class Solution {

// 总节点数
int n;
// 树
// 字符串
String labels;
// 最终结果
int[] result;

public int[] countSubTrees(int n, int[][] edges, String labels) {
this.n = n;
this.labels = labels;
result = new int[n];

// 双向构造树的关系
tree = new HashMap<>(n / 4 * 3 + 1);
for (int[] edge : edges) {
// 添加映射关系
list = tree.computeIfAbsent(edge[0], k -> new LinkedList<>());
list = tree.computeIfAbsent(edge[1], k -> new LinkedList<>());
}

// 深度优先搜索
dfs(0);

return result;
}

public int[] dfs(int index) {
// 当前子树中，所有字符的个数
int[] charArray = new int[26];

// 开始计算，标志该节点已经计算过
result[index] = 1;
// 获得其关联的节点
List<Integer> nodes = tree.get(index);
// 遍历
for (int node : nodes) {
// 如果该节点已经访问过
if (result[node] > 0) {
continue;
}

// 递归遍历子节点
int[] array = dfs(node);
for (int i = 0; i < 26; i++) {
charArray[i] += array[i];
}
}
// 将当前节点的值计算一下
charArray[labels.charAt(index) - 'a'] += 1;
result[index] = charArray[labels.charAt(index) - 'a'];
return charArray;
}
}
```

### 用空间换时间

```    public char charAt(int index) {
if ((index < 0) || (index >= value.length)) {
throw new StringIndexOutOfBoundsException(index);
}
return value[index];
}
```

```class Solution {

// 总节点数
int n;
// 树
// 每个节点的值（用数字表示）
int[] nodeValueArray;
// 最终结果
int[] result;

public int[] countSubTrees(int n, int[][] edges, String labels) {
this.n = n;
nodeValueArray = new int[n];
result = new int[n];

// 双向构造树的关系
for (int i = 0; i < n; i++) {
}
for (int[] edge : edges) {
// 添加映射关系
}

// 生成节点的值
for (int i = 0; i < n; i++) {
nodeValueArray[i] = labels.charAt(i) - 'a';
}

// 深度优先搜索
dfs(0);

return result;
}

public int[] dfs(int index) {
// 当前子树中，所有字符的个数
int[] charArray = new int[26];

// 开始计算，标志该节点已经计算过
result[index] = 1;
// 获得其关联的节点
List<Integer> nodes = tree[index];
// 遍历
for (int node : nodes) {
// 如果该节点已经访问过
if (result[node] > 0) {
continue;
}

// 递归遍历子节点
int[] array = dfs(node);
for (int i = 0; i < 26; i++) {
charArray[i] += array[i];
}
}
// 将当前节点的值计算一下
charArray[nodeValueArray[index]] += 1;
result[index] = charArray[nodeValueArray[index]];
return charArray;
}
}
```

### 研究一下目前最优解法

```public class Solution {

static class Next {

Next next;
Node node;

Next(Next next, Node node) {
this.next = next;
this.node = node;
}
}

static class Node {

/**
* 当前节点的index
*/
final int index;

/**
* 当前节点对应的字符值（减去'a'）
*/
final int ci;

/**
* 所有关联的节点
*/
Next children;

/**
* 该节点的父节点
*/
Node parent;

/**
* 子树中和该节点含有相同字符的节点总个数
*/
int result;

/**
* 是否还在队列中，可以理解为是否已访问过
*/
boolean inQueue;

public Node(int index, int ci) {
this.index = index;
this.ci = ci;
this.result = 1;
}

/**
* 从后往前，找到当前节点没有访问过的第一个子节点
*/
Node popChild() {
for (; ; ) {
// 当前节点的所有关联节点
Next n = this.children;
// 如果没有，说明子节点都遍历完了
if (n == null) {
return null;
}
// 从后往前移除关联节点
this.children = n.next;
// 返回第一个没有访问过的节点
if (!n.node.inQueue) {
return n.node;
}
}
}

/**
* 访问了该节点
*/
Node enqueue(Node[] cnodes) {
// 该节点标记为访问过
this.inQueue = true;
// 记录该节点的父节点
this.parent = cnodes[ci];
// 那么现在该字符值对应的最高节点，就是当前节点。
// 这样如果之后也遇到相同字符的子节点，就可以为子节点赋值其父节点，也就是上面一行是有效的
cnodes[ci] = this;
return this;
}

/**
* 退出该节点
*/
void dequeue(Node[] cnodes, int[] res) {
// 之后会访问该节点的兄弟节点，因此父节点需要重新设置
cnodes[ci] = this.parent;
// 设置当前节点的值
res[index] = this.result;
// 父节点也可以进行累加
if (this.parent != null) {
this.parent.result += this.result;
}
}

// this节点和x节点，互相绑定
this.children = new Next(this.children, x);
x.children = new Next(x.children, this);
}
}

public int[] countSubTrees(int n, int[][] edges, String labels) {
// 构造树
Node[] nodes = new Node[n];
// 每个节点对应的字符
for (int i = 0; i < n; i++) {
nodes[i] = new Node(i, labels.charAt(i) - 'a');
}
// 通过边的关系，将节点互相绑定
for (int[] es : edges) {
}

// 最终的结果
int[] res = new int[n];
// 当前访问的节点下标
int sz = 0;
// 26个小写英文字母对应的节点数组
Node[] cnodes = new Node[26];
// 下面三行可以合并成这一行：
// Node node = nodes[sz++] = nodes[0].enqueue(cnodes);
nodes[sz] = nodes[0].enqueue(cnodes);
// 当前访问的节点
Node node = nodes[sz];
// 因为当前节点已经访问过，自然下标需要+1
sz++;

for (; ; ) {
// 从后往前，找到当前节点没有访问过的第一个子节点
Node child = node.popChild();
// 如果已经全部访问过了
if (child == null) {
// 开始计算
node.dequeue(cnodes, res);
if (--sz == 0) {
break;
}
// 回溯到父节点
node = nodes[sz - 1];
} else {
// 保证了相邻节点一定是父子节点
node = nodes[sz++] = child.enqueue(cnodes);
}
}
return res;
}
}
```

## 总结

https://death00.github.io/

0 条评论

• ### 盘点互联网公司最常见的面试编程题

互联网公司面试，笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说，败在了编程题上，去不了自己心仪的公司，拿不到想要的待遇。

• ### 盘点互联网公司最常见的面试编程题

互联网公司面试，笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说，败在了编程题上，去不了自己心仪的公司，拿不到想要的待遇。

• ### 盘点互联网公司最常见的面试编程题

互联网公司面试，笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说，败在了编程题上，去不了自己心仪的公司，拿不到想要的待遇。

• ### BFS，丑数问题-LeetCode 310、264、313、328、343（拆分链表）

对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找...

• ### LeetCode 310. 最小高度树（图 聪明的BFS，从外向内包围）

对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找...

• ### LeetCode 776. 拆分二叉搜索树（DFS）*

请将该树按要求拆分为两个子树：其中一个子树结点的值都必须小于等于给定的目标值 V；另一个子树结点的值都必须大于目标值 V；树中并非一定要存在值为 V 的结点。

• ### 二叉树问题（二）-LeetCode 965、563、993、958、919（树深度，层次遍历）

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时，才返回 true；否则返回 false。

• ### 二叉树问题（一）-LeetCode 110、617、101、814、655、98、654（递归思路）

给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

• ### 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。