数组二叉树

【编程题目 |200分】数组二叉树【2021 H1,H2 考试题】

时间限制：C/C++ 1秒，其他语言 2秒

空间限制：C/C++262144K，其他语言524288K

64bit IO Format：%lld

本题可使用本地IDE编码，不能使用本地已有代码，无跳出限制，

编码后请点击”保存并调试“按钮进行代码提交。

■ 题目描述

【数组二叉树】

二叉树也可以用数组来存储，给定一个数组，树的根节点的值存储在下标1，对于存储在下标N的节点，它的左子节点和右子节点分别存储在下标2*N和2*N+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

说明

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

代码实现

C++解法一

#include<bits/stdc++.h>

using namespace std;

void SplitString(string input, vector <string> &output, string pattern);

class solution {
public:

剩余50%内容，订阅会员后查看

C++解法二

#include<bits/stdc++.h>

using namespace std;

剩余50%内容，订阅会员后查看

JAVA解法一

import org.jetbrains.annotations.NotNull;

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

public class ArrayBinaryTree {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        while (str != null && !str.equals("")) {
            String[] temp = str.split(" ");
            ArrayList<Integer> array = new ArrayList<>();

剩余50%内容，订阅会员后查看

JAVA解法二

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class ArrayBinaryTree {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String[] strings = sc.nextLine().split(" ");

剩余50%内容，订阅会员后查看

JavaScript

let ints = readLine().split(" ").map(Number);

剩余50%内容，订阅会员后查看

Python解法一

nums = [-1]
res = []
nums[1:] = list(map(int, input().split()))

剩余50%内容，订阅会员后查看

Python解法二

class Node:

    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

剩余50%内容，订阅会员后查看

STICK永久会员

打赏 收藏 海报 链接