题目描述
已知 树形结构 的所有节点信息，现要求根据输入坐标找到该节点保存的内容值
其中表示节点所在的层数，根节点位于第
层，根节点的子节点位于第
层，依次类推
表示节点在该层内的相对偏移，从左至右，第一个节点偏移
，第二个节点偏移
，依次类推
ex：如上图，假定圆圈内的数字表示节点保存的内容值，则根据坐标查到的内容值是
输入描述
每个节点以一维数组 int[]表示所有节点信息构成二维数组 int[][]二维数组的0位置存放根节点表示单节点的一维数组中，0位置保存内容值，后续位置保存子节点在二维数组中的索引位置。对于上图中:
- 根节点的可以表示为
- 表示根节点的内容值是
10，其有两个子节点，在二维数组中的索引分别是1 和 2
- 树的整体表示为
{{10, 1, 2},{-30, 3, 4},{25, 5},{14},{35},{66}} - 查询条件以长度为
2的一维数组表示，上图查询坐标为(2,3)时表示为(2,3) - 使用Java标准IO键盘输入进行录入时.
- 先录入节点数量
- 然后逐行录入节点
- 最后录入查询的位置
对于上述示例为:
6
10 1 2
-30 3 4
25 5
14
35
66
2 2输出描述
查询到内容时，输出{内容值}，查询不到时输出{}上述例子中根据坐标(2,2)查询输出{66}，根据坐标(2,3)查询输出{}
用例
用例1
--输入
6
10 1 2
-30 3 4
25 5
14
35
66
2 2
--输出
{66}
--说明
无用例2
--输入
14
0 1 2 3 4
-11 5 6 7 8
113 9 10 11
24 12
35
66 13
77
88
99
101
102
103
25
104
2 5
--输出
{102}
--说明
无用例3
--输入
14
0 1 2 3 4
-11 5 6 7 8
113 9 10 11
24 12
35
66 13
77
88
99
101
102
103
25
104
3 2
--输出
{}
--说明
无用例4
--输入
1
1000
0 0
--输出
{1000}
--说明
无题目解析
- 首先是对原始数据的接收，适合用
List<List<Integer>>类型的结构来接收 - 那么接下来该怎么处理呢？
- 不如假设现在有了这样一颗树，从第 0 层开始，每一层从 第 0 个节点开始
- 那么目标就是求：第
x层的，第y个节点，BFS 可以解决
- 那么现在的问题就是如何处理原始数据并建树了
- 根据用例数据可以知道，需要建立一颗多叉树
- 具体的建树逻辑过程呢？
- 首先从第一个节点数组开始遍历.
- ex：
[0, 1, 2, 3, 4]这里表示了 根节点有四个子节点，那么该怎么办呢？
- 依次处理这四个子节点，加入到根节点集合中去。
- 那么现在问题来了，索引下标为 1 的节点被处理过了，那么来到节点 1 数据集合
- ex:
-11 5 6 7 8其值为-11，现在很显然-11已经被加入到树结构中了，那么现在如何判断树结构中已经有了 11 - 这一点好像不太好处理.
- 那么换一种思路，dfs 建树.
- 对于原始集合
List<List<Integer>>中的每一个子list都有着相同的逻辑 - 签名函数需要有什么呢？首先可以肯定的是，能够拿到当前的子
list - 签名函数和终止条件
- 其父节点，因为要把当前节点加入到其父节点中去.
- 然后处理其子节点，如果没有子节点，那么逻辑执行到当前节点加入到父节点集合中就可以结束了
show code
package com.hw;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
/**
* desc : <a href="https://fcqian.blog.csdn.net/article/details/128274181">查找树中元素</a>
* <p>
* create time : 2023/7/28 10:12
*/
public class TreeSearchEle {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextLine()) {
int nodeNum = Integer.parseInt(in.nextLine());
List<List<Integer>> nodeList = new ArrayList<>();
for (int i = 0; i < nodeNum; i++) {
String[] split = in.nextLine().split(" ");
List<Integer> node = new ArrayList<>();
for (String s : split) {
node.add(Integer.parseInt(s));
}
nodeList.add(node);
}
String[] coordinate = in.nextLine().split(" ");
int x = Integer.parseInt(coordinate[0]);
int y = Integer.parseInt(coordinate[1]);
treeSearchEle(nodeNum, nodeList, x, y);
}
}
private static void treeSearchEle(int nodeNum, List<List<Integer>> nodeList, int x, int y) {
// step 1. dfs建树.
MultiTree root = dfs(null, nodeList, 0);
// step 2. 查树.
LinkedList<MultiTree> queue = new LinkedList<>();
queue.offer(root);
int level = 0;
while(!queue.isEmpty()) {
int sz = queue.size();
if(level == x) {
if(sz < y + 1) {
System.out.println("{}");
return;
}
while (y > 0) {
queue.removeFirst();
y--;
}
int val = queue.getFirst().val;
System.out.println("{"+val+"}");
return;
}
for (int i = 0; i < sz; i++) {
if(queue.getFirst().child != null && queue.getFirst().child.size() > 0) {
queue.addAll(queue.removeFirst().child);
} else {
queue.removeFirst();
}
}
level++;
}
}
// idx : 当前节点的索引.
private static MultiTree dfs(MultiTree parent, List<List<Integer>> nodeList, int idx) {
// 创建当前节点
MultiTree localNode = new MultiTree(nodeList.get(idx).get(0));
if(localNode.child == null && nodeList.get(idx).size() > 1) {
localNode.child = new ArrayList<MultiTree>();
}
// 处理当前节点的子节点
for (int i = 1; i < nodeList.get(idx).size(); i++) {
localNode.child.add(dfs(localNode, nodeList, nodeList.get(idx).get(i)));
}
return localNode;
}
}
class MultiTree {
public int val;
public List<MultiTree> child;
public MultiTree(int val) {
this.val = val;
}
}