### 华为OD机试C卷- 数组二叉树（Java & JS & Python）
#### 颈椎题目概述
本题目主要考察的是利用数组来表示二叉树，并且通过深度优先搜索（DFS）的方式寻找从根节点到最小叶子节点的路径。题目描述中给出了非常清晰的数据结构和操作流程：
- **数据结构**：使用数组存储二叉树，其中数组的下标1代表树的根节点。对于数组下标为`N`的节点，其左子节点存储在`2N`位置，右子节点存储在`2N + 1`位置。数组中的-1表示该位置对应的节点为空。
- **任务**：给定一个这样的数组表示的二叉树，找出从根节点到最小叶子节点的路径，路径上的节点值按顺序排列输出。
#### 输入输出说明
- **输入**：一行包含多个正整数，这些整数用空格分隔，代表数组的内容。数组的第一个元素即为根节点的值。
- **输出**：从根节点到最小叶子节点的路径上各个节点的值，节点值之间用空格分隔。
#### 解题思路
此题可以使用深度优先搜索（DFS）进行解题，DFS是一种用于遍历或搜索树或图的算法。在二叉树中，DFS可以从根节点开始向下探索每一个分支直到叶子节点。对于寻找最小叶子节点路径的问题，DFS特别适用，因为它可以在发现一条路径后立即返回，而不需要等待遍历完整棵树。
#### 代码实现分析
##### Java 实现
```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BinaryTreePath {
private static List<Integer> minPath = null;
private static int minVal = Integer.MAX_VALUE;
public static void dfs(int[] tree, int index, List<Integer> path) {
if (index > tree.length || tree[index] == -1) return; // 越界或空节点
path.add(tree[index]); // 添加当前节点到路径
// 如果是叶子节点，则更新最小路径
if (2 * index > tree.length || (tree[2 * index] == -1 && tree[2 * index + 1] == -1)) {
if (tree[index] < minVal) {
minVal = tree[index];
minPath = new ArrayList<>(path);
}
}
// 递归遍历左右子树
dfs(tree, 2 * index, path);
dfs(tree, 2 * index + 1, path);
path.remove(path.size() - 1); // 回溯，移除当前节点
}
public static List<Integer> findMinPath(int[] tree) {
minPath = null;
minVal = Integer.MAX_VALUE;
List<Integer> path = new ArrayList<>();
dfs(tree, 1, path);
return minPath;
}
public static void main(String[] args) {
int[] tree = {1, 2, 3, -1, -1, 4, 5};
List<Integer> result = findMinPath(tree);
System.out.println(String.join(" ", result.stream().map(Object::toString).toArray(String[]::new)));
}
}
```
##### Python 实现
```python
def dfs(tree, index, path, min_path, min_val):
if index > len(tree) - 1 or tree[index] == -1:
return
path.append(tree[index]) # 添加当前节点到路径
# 如果是叶子节点，则更新最小路径
if 2 * index > len(tree) - 1 or (tree[2 * index] == -1 and tree[2 * index + 1] == -1):
if tree[index] < min_val:
min_val = tree[index]
min_path[:] = path[:] # 复制当前路径
# 递归遍历左右子树
dfs(tree, 2 * index, path, min_path, min_val)
dfs(tree, 2 * index + 1, path, min_path, min_val)
path.pop() # 回溯，移除当前节点
# 测试代码
tree = [1, 2, 3, -1, -1, 4, 5]
min_path = []
min_val = float('inf')
dfs(tree, 1, [], min_path, min_val)
print(min_path)
```
### 总结
通过上述代码示例可以看出，在Java和Python两种语言中实现该问题的解决方案时，核心逻辑是相似的，都采用了深度优先搜索的方法。不同之处在于语法细节和内置函数的使用。这种题目不仅可以锻炼对数据结构的理解能力，还可以提升对算法的应用能力。在实际应用中，这种类型的题目对于理解复杂数据结构及其操作具有重要意义。
