跳至主要內容

2025A-数组二叉树

题目描述与示例

题目描述

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

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

题目练习网址：https://www.algomooc.com/problem/P3607

输入描述

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

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

输入的树最多为7层。

输出描述

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

示例一

输入

3 5 7 -1 -1 2 4

输出

3 7 2

示例二

输入

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

输出

5 8 7 6

说明

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

解题思路

关于二叉树的基础内容可以详见二叉树专题小班里的内容。

本题分为两个部分，一是根据输入还原出这棵二叉树，二是根据这棵二叉树找到从根节点到最小叶节点的路径。

还原二叉树

还原二叉树的过程和题目【DFS】2024E-完全二叉树非叶子部分后序遍历是非常类似的。

二叉树的节点类使用最普通的构造方法即可，包含左节点、右节点、值三个成员变量。

class Node:
    def __init__(self, val = 0, left = None, right = None):
        self.val = 0
        self.left = left
        self.right = right

容易发现：按照题目所示的输入数组lst，该数组中索引为i的节点，其左、右节点在lst中的索引为2*i+1和2*i+2。

特别注意，此处不要被题目中**“下标从1开始表示根节点”**的字眼所迷惑。因为实际给定的数组里，下标0在树的表示中没有被使用而被忽略。

要么你需要手动地在数组开头（下标0）填充一个无关值，要么就应该认为根节点位于下标0的位置。

本文的后续内容都是按照后者的处理方式来进行的。

如果选择了前一种处理方式，则该数组中索引为i的节点，其左、右节点在lst中的索引为题目中所说的2*i和2*i+1。

譬如对于例子

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

构建出的二叉树如下

暂时无法在飞书文档外展示此内容

图中红色的节点表示实际存在的节点，实线箭头表示实际存在的连接关系。

图中灰色的节点表示不存在的空节点，虚线箭头表示实际上不存在的连接关系。

容易发现几个有意思的特点：

  1. 如果把输入数组中的所有的-1删除，将会得到二叉树的层序遍历结果。
  2. 如果把这些-1所代表的空节点看成是实际存在的节点，那么这棵二叉树就是一棵完全二叉树。
  3. 在输入数组中，这些-1的存在是必不可少的，因为每一个-1都起到在这棵假想的完全二叉树中进行占位的作用。

再举一个例子，假设输入为

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

在6前面多了一个-1，那么将代表以下这棵树

暂时无法在飞书文档外展示此内容

和前一个例子将有所区别。

类似【DFS】2024E-完全二叉树非叶子部分后序遍历 中的构造方法，我们可以构建buildNode()递归函数。

由于可能出现-1表示空节点，所以需要对val多加一个判断条件，以提前终止函数。

def buildNode(n, lst, i):
    val = lst[i]
    # 如果遇到-1，说明这是一个空节点，直接返回None
    if val == -1:
        return None

    # 初始化左、右子节点为None
    left, right = None, None

    # 如果左节点存在
    if 2 * i + 1 < n:
        # 构建左节点left
        left = buildNode(n, lst, 2 * i + 1)

    # 如果右节点存在
    if 2 * i + 2 < n:
        # 构建右节点right
        right = buildNode(n, lst, 2 * i + 2)

    # 构建当前节点，传入值、左节点、右节点三个实参
    cur = Node(val, left, right)
    return cur

还可以继续优化上述函数

def buildNode(n, lst, i):
    # 构建左、右子树
    left = buildNode(n, lst, 2*i+1) if 2*i+1 < n else None
    right = buildNode(n, lst, 2*i+2) if 2*i+2 < n else None
        
    # 构建当前节点，传入值、左节点、右节点三个实参
    cur = Node(lst[i], left, right) if lst[i] != -1 else None
    return cur

甚至一行写完

def buildNode(n, lst, i):
    # 构建当前节点，传入值、左节点、右节点三个实参
    return Node(lst[i], buildNode(n, lst, 2*i+1) if 2*i+1 < n else None, buildNode(n, lst, 2*i+2) if 2*i+2 < n else None) if lst[i] != -1 else None

对应的递归入口调用也非常简单，即

root = buildNode(n, lst, 0)

就能得到根节点root了。

找到最小叶子节点

在得到根节点之后，遍历整棵二叉树，先找到最小叶子节点。构建递归函数find()。

from math import inf

def find(node):
    global min_leaf
    # 如果左右节点均不存在，说明当前节点是一个叶子节点
    if not node.left and not node.right:
        # 更新min_leaf并终止递归
        min_leaf = min(node.val, min_leaf)
        return
    # 如果左节点存在，递归调用左节点
    if node.left:
        find(node.left)
    # 如果右节点存在，递归调用右节点
    if node.right:
        find(node.right)


# 初始化min_leaf，表示最小叶节点
min_leaf = inf
# 递归函数的递归入口
find(root)

此处使用前序遍历来遍历整棵二叉树，实际上此处使用中序或后序遍历均可以。

找到到达最小叶子节点的路径

为了找到路径，我们还需要同时记录遍历过程中的路径

我们需要再添加一个路径变量path，并且在每次递归时修改path，此处是一个回溯过程。

另外，关于递归终止时，ans更新的部分也要进行修改。

from math import inf

def find(node, path):
    global min_leaf, ans
    # 如果左右节点均不存在，说明当前节点是一个叶子节点
    if not node.left and not node.right:
        # 更新min_leaf和ans，并终止递归
        if min_leaf > node.val:
            min_leaf = node.val
            ans = " ".join(map(str, path))
        return
    # 如果左节点存在，递归调用左节点
    if node.left:
        find(node.left, path + [node.left.val])
    # 如果右节点存在，递归调用右节点
    if node.right:
        find(node.right, path + [node.right.val])

# 初始化min_leaf，表示最小叶节点
min_leaf = inf
# 初始化答案变量ans，为一个空字符串
ans = ""
# 递归函数的递归入口
find(root, [root.val])

或者将path的更新和回滚显示地写出

from math import inf

# 寻找最小叶子节点，且找到从根节点到最小叶子节点路径的函数
def find(node, path):
    global min_leaf, ans
    # 如果左右节点均不存在，说明当前节点是一个叶子节点
    if not node.left and not node.right:
        # 更新min_leaf和ans，并终止递归
        if min_leaf > node.val:
            min_leaf = min(node.val, min_leaf)
            ans = " ".join(map(str, path))
        return
    # 如果左节点存在，递归调用左节点
    if node.left:
        # 状态更新
        path.append(node.left.val)
        # 回溯
        find(node.left, path)
        # 回滚
        path.pop()
    # 如果右节点存在，递归调用右节点
    if node.right:
        # 状态更新
        path.append(node.right.val)
        # 回溯
        find(node.right, path)
        # 回滚
        path.pop()

# 初始化min_leaf，表示最小叶节点
min_leaf = inf
# 初始化答案变量ans，为一个空字符串
ans = ""
# 递归函数的递归入口
find(root, [root.val])

综上本题基本就解决了。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

from math import inf


# 定义树节点的类，包括
# 值val，左节点left，右节点right，
class Node:
   def __init__(self, val, left, right):
       self.val = val
       self.left = left
       self.right = right


# 构建二叉树的函数
def buildNode(n, lst, i):
    val = lst[i]
    # 如果遇到-1，说明这是一个空节点，直接返回None
    if val == -1:
        return None

    # 初始化左、右子节点为None
    left, right = None, None

    # 如果左节点存在
    if 2 * i + 1 < n:
        # 构建左节点left
        left = buildNode(n, lst, 2 * i + 1)

    # 如果右节点存在
    if 2 * i + 2 < n:
        # 构建右节点right
        right = buildNode(n, lst, 2 * i + 2)

    # 构建当前节点，传入值、左节点、右节点三个实参
    cur = Node(val, left, right)
    return cur


# 寻找最小叶子节点，且找到从根节点到最小叶子节点路径的函数
def find(node, path):
    global min_leaf, ans
    # 如果左右节点均不存在，说明当前节点是一个叶子节点
    if not node.left and not node.right:
        # 更新min_leaf和ans，并终止递归
        if min_leaf > node.val:
            min_leaf = min(node.val, min_leaf)
            ans = " ".join(map(str, path))
        return
    # 如果左节点存在，递归调用左节点
    if node.left:
        # 状态更新
        path.append(node.left.val)
        # 回溯
        find(node.left, path)
        # 回滚
        path.pop()
    # 如果右节点存在，递归调用右节点
    if node.right:
        # 状态更新
        path.append(node.right.val)
        # 回溯
        find(node.right, path)
        # 回滚
        path.pop()


# 输入表示二叉树的数组
lst = list(map(int, input().split()))
# 获得数组长度
n = len(lst)
# 构建根节点，还原整棵二叉树
root = buildNode(n, lst, 0)
# 初始化min_leaf，表示最小叶节点
min_leaf = inf
# 初始化答案变量ans，为一个空字符串
ans = ""
# 递归函数的递归入口
find(root, [root.val])
# 输出答案
print(ans)

Java

import java.util.*;

class Node {
    int val;         // 节点值
    Node left;       // 左节点
    Node right;      // 右节点

    // 构造函数
    Node(int val, Node left, Node right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Main {

    static int minLeaf = Integer.MAX_VALUE; // 最小叶子节点值
    static String ans = "";                 // 保存路径的答案

    // 构建二叉树的函数
    public static Node buildNode(int n, int[] lst, int i) {
        int val = lst[i];  // 当前节点的值
        // 如果遇到 -1，说明这是一个空节点，直接返回 null
        if (val == -1) {
            return null;
        }

        Node left = null, right = null;

        // 如果左节点存在
        if (2 * i + 1 < n) {
            left = buildNode(n, lst, 2 * i + 1);
        }

        // 如果右节点存在
        if (2 * i + 2 < n) {
            right = buildNode(n, lst, 2 * i + 2);
        }

        // 构建当前节点
        return new Node(val, left, right);
    }

    // 寻找最小叶子节点，且找到从根节点到最小叶子节点路径的函数
    public static void find(Node node, List<Integer> path) {
        // 如果左右节点均不存在，说明当前节点是一个叶子节点
        if (node.left == null && node.right == null) {
            // 更新 minLeaf 和 ans
            if (minLeaf > node.val) {
                minLeaf = node.val;
                ans = String.join(" ", path.stream().map(String::valueOf).toArray(String[]::new));
            }
            return;
        }

        // 如果左节点存在，递归调用左节点
        if (node.left != null) {
            path.add(node.left.val); // 状态更新
            find(node.left, path);   // 递归
            path.remove(path.size() - 1); // 回滚
        }

        // 如果右节点存在，递归调用右节点
        if (node.right != null) {
            path.add(node.right.val); // 状态更新
            find(node.right, path);   // 递归
            path.remove(path.size() - 1); // 回滚
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入表示二叉树的数组
        String[] input = scanner.nextLine().split(" ");
        int n = input.length;

        int[] lst = new int[n];
        for (int i = 0; i < n; i++) {
            lst[i] = Integer.parseInt(input[i]);
        }

        // 构建根节点，还原整棵二叉树
        Node root = buildNode(n, lst, 0);

        // 初始化路径
        List<Integer> path = new ArrayList<>();
        path.add(root.val);

        // 递归函数的递归入口
        find(root, path);

        // 输出答案
        System.out.println(ans);

        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <climits>
#include <sstream>

using namespace std;

// 定义树节点的结构体
struct Node {
    int val;      // 节点值
    Node* left;   // 左节点
    Node* right;  // 右节点

    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

// 构建二叉树的函数
Node* buildNode(int n, const vector<int>& lst, int i) {
    int val = lst[i];
    // 如果遇到-1，说明这是一个空节点，直接返回nullptr
    if (val == -1) {
        return nullptr;
    }

    Node* left = nullptr;
    Node* right = nullptr;

    // 如果左节点存在
    if (2 * i + 1 < n) {
        left = buildNode(n, lst, 2 * i + 1);
    }

    // 如果右节点存在
    if (2 * i + 2 < n) {
        right = buildNode(n, lst, 2 * i + 2);
    }

    // 构建当前节点
    return new Node(val, left, right);
}

int minLeaf = INT_MAX;  // 最小叶子节点值
string ans = "";        // 保存路径的答案

// 寻找最小叶子节点，且找到从根节点到最小叶子节点路径的函数
void find(Node* node, vector<int>& path) {
    // 如果左右节点均不存在，说明当前节点是一个叶子节点
    if (node->left == nullptr && node->right == nullptr) {
        // 更新 minLeaf 和 ans，并终止递归
        if (minLeaf > node->val) {
            minLeaf = node->val;

            // 更新答案路径
            ans = "";
            for (size_t i = 0; i < path.size(); ++i) {
                if (i > 0) ans += " ";
                ans += to_string(path[i]);
            }
        }
        return;
    }

    // 如果左节点存在，递归调用左节点
    if (node->left != nullptr) {
        path.push_back(node->left->val); // 状态更新
        find(node->left, path);         // 递归
        path.pop_back();                // 回滚
    }

    // 如果右节点存在，递归调用右节点
    if (node->right != nullptr) {
        path.push_back(node->right->val); // 状态更新
        find(node->right, path);         // 递归
        path.pop_back();                 // 回滚
    }
}

int main() {
    string input;
    getline(cin, input);

    // 解析输入
    stringstream ss(input);
    vector<int> lst;
    int value;
    while (ss >> value) {
        lst.push_back(value);
    }

    int n = lst.size();

    // 构建根节点，还原整棵二叉树
    Node* root = buildNode(n, lst, 0);

    // 初始化路径
    vector<int> path = {root->val};

    // 递归函数的递归入口
    find(root, path);

    // 输出答案
    cout << ans << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

// 定义树节点的结构体
typedef struct Node {
    int val;          // 节点值
    struct Node* left;  // 左节点
    struct Node* right; // 右节点
} Node;

// 创建一个新的节点
Node* createNode(int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 构建二叉树的函数
Node* buildNode(int n, int* lst, int i) {
    int val = lst[i];
    // 如果遇到-1，说明这是一个空节点，直接返回NULL
    if (val == -1) {
        return NULL;
    }

    Node* left = NULL;
    Node* right = NULL;

    // 如果左节点存在
    if (2 * i + 1 < n) {
        left = buildNode(n, lst, 2 * i + 1);
    }

    // 如果右节点存在
    if (2 * i + 2 < n) {
        right = buildNode(n, lst, 2 * i + 2);
    }

    // 构建当前节点
    Node* current = createNode(val);
    current->left = left;
    current->right = right;
    return current;
}

int minLeaf = INT_MAX;  // 最小叶子节点值
char* ans = NULL;       // 保存路径的答案

// 寻找最小叶子节点，且找到从根节点到最小叶子节点路径的函数
void find(Node* node, int* path, int pathLen) {
    // 如果左右节点均不存在，说明当前节点是一个叶子节点
    if (node->left == NULL && node->right == NULL) {
        // 更新 minLeaf 和 ans，并终止递归
        if (minLeaf > node->val) {
            minLeaf = node->val;

            // 更新答案路径
            free(ans); // 释放之前分配的内存
            ans = (char*)malloc(1024); // 分配足够大的空间
            ans[0] = '\0';
            for (int i = 0; i < pathLen; ++i) {
                char buffer[32];
                sprintf(buffer, "%d", path[i]);
                strcat(ans, buffer);
                if (i < pathLen - 1) {
                    strcat(ans, " ");
                }
            }
        }
        return;
    }

    // 如果左节点存在，递归调用左节点
    if (node->left != NULL) {
        path[pathLen] = node->left->val; // 状态更新
        find(node->left, path, pathLen + 1); // 递归
    }

    // 如果右节点存在，递归调用右节点
    if (node->right != NULL) {
        path[pathLen] = node->right->val; // 状态更新
        find(node->right, path, pathLen + 1); // 递归
    }
}

int main() {
    char input[4096];
    fgets(input, sizeof(input), stdin);

    // 解析输入
    int lst[1024];
    int n = 0;
    char* token = strtok(input, " ");
    while (token != NULL) {
        lst[n++] = atoi(token);
        token = strtok(NULL, " ");
    }

    // 构建根节点，还原整棵二叉树
    Node* root = buildNode(n, lst, 0);

    // 初始化路径
    int* path = (int*)malloc(n * sizeof(int));
    path[0] = root->val;

    // 递归函数的递归入口
    find(root, path, 1);

    // 输出答案
    printf("%s\n", ans);

    // 释放内存
    free(path);
    free(ans);

    return 0;
}

Node JavaScript

class Node {
    constructor(val, left = null, right = null) {
        this.val = val; // 节点值
        this.left = left; // 左节点
        this.right = right; // 右节点
    }
}

let minLeaf = Infinity; // 最小叶子节点值
let ans = ""; // 保存路径的答案

// 构建二叉树的函数
function buildNode(n, lst, i) {
    const val = lst[i]; // 当前节点的值
    // 如果遇到 -1，说明这是一个空节点，直接返回 null
    if (val === -1) {
        return null;
    }

    let left = null, right = null;

    // 如果左节点存在
    if (2 * i + 1 < n) {
        left = buildNode(n, lst, 2 * i + 1);
    }

    // 如果右节点存在
    if (2 * i + 2 < n) {
        right = buildNode(n, lst, 2 * i + 2);
    }

    // 构建当前节点
    return new Node(val, left, right);
}

// 寻找最小叶子节点，且找到从根节点到最小叶子节点路径的函数
function find(node, path) {
    // 如果左右节点均不存在，说明当前节点是一个叶子节点
    if (!node.left && !node.right) {
        // 更新 minLeaf 和 ans
        if (minLeaf > node.val) {
            minLeaf = node.val;
            ans = path.join(" ");
        }
        return;
    }

    // 如果左节点存在，递归调用左节点
    if (node.left) {
        path.push(node.left.val); // 状态更新
        find(node.left, path); // 递归
        path.pop(); // 回滚
    }

    // 如果右节点存在，递归调用右节点
    if (node.right) {
        path.push(node.right.val); // 状态更新
        find(node.right, path); // 递归
        path.pop(); // 回滚
    }
}

// 主函数
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question("", (input) => {
    const lst = input.split(" ").map(Number);
    const n = lst.length;

    // 构建根节点，还原整棵二叉树
    const root = buildNode(n, lst, 0);

    // 初始化路径
    const path = [root.val];

    // 递归函数的递归入口
    find(root, path);

    // 输出答案
    console.log(ans);

    rl.close();
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
        "math"
)

// 定义树节点的结构体
type Node struct {
        val   int   // 节点值
        left  *Node // 左节点
        right *Node // 右节点
}

// 构建二叉树的函数
func buildNode(n int, lst []int, i int) *Node {
        val := lst[i]
        // 如果遇到 -1，说明这是一个空节点，直接返回 nil
        if val == -1 {
                return nil
        }

        var left, right *Node

        // 如果左节点存在
        if 2*i+1 < n {
                left = buildNode(n, lst, 2*i+1)
        }

        // 如果右节点存在
        if 2*i+2 < n {
                right = buildNode(n, lst, 2*i+2)
        }

        // 构建当前节点
        return &Node{val: val, left: left, right: right}
}

var minLeaf = math.MaxInt32 // 最小叶子节点值
var ans = ""                // 保存路径的答案

// 寻找最小叶子节点，且找到从根节点到最小叶子节点路径的函数
func find(node *Node, path []int) {
        // 如果左右节点均不存在，说明当前节点是一个叶子节点
        if node.left == nil && node.right == nil {
                // 更新 minLeaf 和 ans
                if minLeaf > node.val {
                        minLeaf = node.val
                        ans = strings.Trim(strings.Replace(fmt.Sprint(path), " ", " ", -1), "[]")
                }
                return
        }

        // 如果左节点存在，递归调用左节点
        if node.left != nil {
                path = append(path, node.left.val) // 状态更新
                find(node.left, path)             // 递归
                path = path[:len(path)-1]         // 回滚
        }

        // 如果右节点存在，递归调用右节点
        if node.right != nil {
                path = append(path, node.right.val) // 状态更新
                find(node.right, path)              // 递归
                path = path[:len(path)-1]           // 回滚
        }
}

func main() {
        reader := bufio.NewReader(os.Stdin)
        input, _ := reader.ReadString('\n')
        input = strings.TrimSpace(input)
        values := strings.Split(input, " ")
        n := len(values)

        lst := make([]int, n)
        for i, v := range values {
                lst[i], _ = strconv.Atoi(v)
        }

        // 构建根节点，还原整棵二叉树
        root := buildNode(n, lst, 0)

        // 初始化路径
        path := []int{root.val}

        // 递归函数的递归入口
        find(root, path)

        // 输出答案
        fmt.Println(ans)
}

时空复杂度

时间复杂度：O(N)。无论是还原二叉树还是遍历二叉树，每一个节点都仅需要经过一次。

空间复杂度：O(1)。除了输入的序列且忽略输入使用的编译栈空间，仅需若干常数变量维护遍历过程。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法