题解

题目描述

给定一个数组，表示一个二叉树的节点值，树的根节点的值存储在下标 1。对于存储在下标 N 的节点，它的左子节点和右子节点分别存储在下标 2N 和 2N+1，并且用值 -1 代表一个节点为空。要求找到从根节点到最小叶子节点的路径，路径由节点的值组成。

题解思路

1. 查找最小叶子节点：
   • 遍历数组，找到所有的叶子节点，并记录最小值及其索引。
2. 路径回溯：从找到的最小叶子节点向上追溯到根节点，构建路径。

复杂度分析

• 时间复杂度：O(N)，其中 N 是节点的数量。每个节点最多被访问一次。
• 空间复杂度：O(H)，H 是树的高度，最坏情况下为 O(N)（在树完全倾斜时），最好的情况下为 O(log N)。

Python 代码

import sys
from typing import List

nums = []         # 存储二叉树节点的值
minLeafPath = []  # 存储从根到最小叶子节点的路径索引

# 深度优先搜索函数，返回当前节点及其子树中的最小叶子节点值
def dfs(index: int) -> int:
    # 检查当前索引是否越界
    if index >= len(nums) or nums[index] == -1:
        return float('inf')
    
    left_index = 2 * index + 1  # 左子节点索引
    right_index = 2 * index + 2 # 右子节点索引

    # 如果是叶子节点
    if left_index >= len(nums):
        minLeafPath[index] = -1  # 标记为叶子节点
        return nums[index]       # 返回当前节点的值

    # 递归查找左右子树中的最小叶子节点值
    minleft = dfs(left_index)
    minright = dfs(right_index)

    # 选择较小的叶子节点路径
    if minleft < minright:
        minLeafPath[index] = left_index
    else:
        minLeafPath[index] = right_index
    if minleft == float('inf') and minright == float('inf'):
        minLeafPath[index] = -1

    # 返回当前子树中的最小叶子节点值
    return min(minleft, minright)

# 读取输入的节点值
for line in sys.stdin:
    nums.extend(map(int, line.split()))

# 初始化 minLeafPath 数组
minLeafPath = [0] * len(nums)

# 从根节点（索引 0）开始深度优先搜索
dfs(0)

# 输出从根节点到最小叶子节点的路径
now = 0
while True:
    print(nums[now], end=" ")
    if minLeafPath[now] == -1:
        break
    now = minLeafPath[now]
print()

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> nums;        // 存储二叉树节点的值
vector<int> minLeafPath; // 存储从根到最小叶子节点的路径索引

// 深度优先搜索函数，返回当前节点及其子树中的最小叶子节点值
int dfs(int index) {
    // 检查当前索引是否越界
    if (index >= nums.size() || nums[index] == -1) return INT_MAX;

    int left_index = 2 * index + 1;  // 左子节点索引
    int right_index = 2 * index + 2; // 右子节点索引

    // 如果是叶子节点
    if (left_index >= nums.size()) {
        minLeafPath[index] = -1; // 标记为叶子节点
        return nums[index];       // 返回当前节点的值
    }

    // 递归查找左右子树中的最小叶子节点值
    int minleft = dfs(left_index);
    int minright = dfs(right_index);

    // 选择较小的叶子节点路径
    if (minleft < minright) {
        minLeafPath[index] = left_index; // 更新路径到左子节点
    } else {
        minLeafPath[index] = right_index; // 更新路径到右子节点
    }
    if(INT_MAX==minleft&&INT_MAX==minright){
        minLeafPath[index]=-1;
    }

    // 返回当前子树中的最小叶子节点值
    return min({minleft, minright});
}

int main() {
    int num;
    // 读取输入的节点值
    while (cin >> num) {
        nums.push_back(num);
    }

    // 初始化 minLeafPath 数组
    minLeafPath.resize(nums.size());

    // 从根节点（索引 0）开始深度优先搜索
    dfs(0);

    // 输出从根节点到最小叶子节点的路径
    int now = 0;
    while (true) {
        cout << nums[now] << " ";
        if (minLeafPath[now] == -1) break; // 到达叶子节点，停止输出
        now = minLeafPath[now]; // 更新当前节点为下一节点
    }
    cout << endl;

    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static List<Integer> nums = new ArrayList<>();         // 存储二叉树节点的值
    static List<Integer> minLeafPath = new ArrayList<>();  // 存储从根到最小叶子节点的路径索引

    // 深度优先搜索函数，返回当前节点及其子树中的最小叶子节点值
    static int dfs(int index) {
        // 检查当前索引是否越界
        if (index >= nums.size() || nums.get(index) == -1) return Integer.MAX_VALUE;

        int leftIndex = 2 * index + 1;   // 左子节点索引
        int rightIndex = 2 * index + 2;  // 右子节点索引

        // 如果是叶子节点
        if (leftIndex >= nums.size()) {
            minLeafPath.set(index, -1);  // 标记为叶子节点
            return nums.get(index);      // 返回当前节点的值
        }

        // 递归查找左右子树中的最小叶子节点值
        int minLeft = dfs(leftIndex);
        int minRight = dfs(rightIndex);

        // 选择较小的叶子节点路径
        if (minLeft < minRight) {
            minLeafPath.set(index, leftIndex);
        } else {
            minLeafPath.set(index, rightIndex);
        }
        if (minLeft == Integer.MAX_VALUE && minRight == Integer.MAX_VALUE) {
            minLeafPath.set(index, -1);
        }

        // 返回当前子树中的最小叶子节点值
        return Math.min(minLeft, minRight);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入的节点值
        while (scanner.hasNextInt()) {
            nums.add(scanner.nextInt());
        }
        
        // 初始化 minLeafPath 数组
        for (int i = 0; i < nums.size(); i++) {
            minLeafPath.add(0);
        }

        // 从根节点（索引 0）开始深度优先搜索
        dfs(0);

        // 输出从根节点到最小叶子节点的路径
        int now = 0;
        while (true) {
            System.out.print(nums.get(now) + " ");
            if (minLeafPath.get(now) == -1) break;
            now = minLeafPath.get(now);
        }
        System.out.println();

        scanner.close();
    }
}

题目描述

二叉树也可以用数组来存储，给定一个数组，树的根节点的值存储在下标$1$，对于存储在下标$N$的节点，它的左子节点和右子节点分别存储在下标$2N$和$2N+1$，并且我们用值$-1$代表一个节点为空。

给定一个数组存储的二叉树，试求从根节点到最小的叶子节点的路径，路径由节点的值组成。

输入描述

输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分隔。

注意第一个元素即为根节点的值，即数组的第$N$个元素对应下标$N$，下标$0$在树的表示中没有使用，所以我们省略了。

输入的树最多为$7$层。

输出描述

输出从根节点到最小叶子节点的路径上，各个节点的值，由空格分隔，用例保证最小叶子节点只有一个。

样例1

输入

3 5 7 -1 -1 2 4

输出

3 7 2

说明

最小叶子节点的路径为$3$ $7$ $2$。

样例2

输入

5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6

输出

5 8 7 6

说明

最小叶子节点的路径为$5$ $8$ $7$ $6$，注意数组仅存储至最后一个非空节点，故不包含节点“$7$”右子节点的$-1$。