已知一颗树的结点序列以及每个结点的度,构造树的兄弟孩子链表,请给我这道题的代码
时间: 2024-02-03 21:11:28 浏览: 70
以下是该问题的一个 Java 实现:
```java
class TreeNode {
int val;
TreeNode firstChild;
TreeNode nextSibling;
public TreeNode(int val) {
this.val = val;
firstChild = null;
nextSibling = null;
}
}
public class TreeBuilder {
public static TreeNode buildTree(int[] nodes, int[] degrees) {
if (nodes == null || degrees == null || nodes.length != degrees.length || nodes.length == 0) {
return null;
}
TreeNode[] treeNodeArr = new TreeNode[nodes.length];
for (int i = 0; i < nodes.length; i++) {
treeNodeArr[i] = new TreeNode(nodes[i]);
}
TreeNode root = treeNodeArr[0];
int idx = 1;
for (int i = 0; i < degrees.length; i++) {
TreeNode cur = treeNodeArr[i];
int degree = degrees[i];
for (int j = 0; j < degree; j++) {
if (idx >= nodes.length) {
break;
}
TreeNode child = treeNodeArr[idx];
if (cur.firstChild == null) {
cur.firstChild = child;
} else {
TreeNode sibling = cur.firstChild;
while (sibling.nextSibling != null) {
sibling = sibling.nextSibling;
}
sibling.nextSibling = child;
}
idx++;
}
}
return root;
}
}
```
这里的 `buildTree` 方法接收两个数组,分别为结点列表和度数列表。函数的返回值为根结点。在函数内部,我们先创建了一个 `TreeNode` 数组,表示每个结点。然后,我们通过遍历度数列表来构建每个结点的兄弟孩子链表。具体来说,我们首先遍历到一个结点,然后根据它的度数,遍历它的每个孩子,并将其链接到该结点的兄弟孩子链表中。最后,我们返回根结点。
需要注意的是,上面的实现并没有考虑到度数为 0 的结点,如果输入中存在度数为 0 的结点,则需要进行特殊处理。
阅读全文