题解

题目描述

给定一个通过顺序储存结构存储整数值的完全二叉树序列（最多1000个整数），请找出此完全二叉树的所有非叶子节点部分，并采用后序遍历方式将这些节点输出。只有一个节点的树，此节点认定为根节点（非叶子）。

完全二叉树定义

• 完全二叉树是一种每一层都被完全填满，除了最后一层可能不满外，且最后一层的节点都尽量集中在左边的树。
• 对于完全二叉树，父节点和子节点的索引有固定关系：
  • 父节点的索引 i，其左子节点的索引为 2*i + 1，右子节点的索引为 2*i + 2。
  • 子节点的父节点索引为 (i-1)/2（向下取整）。

要求

1. 找到非叶子节点部分。
2. 对非叶子节点部分进行后序遍历：左子树 -> 右子树 -> 根节点。

输入描述

一个通过空格分割的整数序列，表示二叉树的节点值，最多1000个整数。

输出描述

非叶子节点部分的后序遍历输出，输出数字以空格分隔。

思路分析

1. 非叶子节点的识别

• 完全二叉树的节点序列中的所有节点，索引从 0 开始。
• 如果一个节点是根节点，则它是非叶子节点。
• 如果一个节点的右子节点存在（即 2*i + 2 小于数组长度），它也是非叶子节点。

2. 后序遍历的定义

• 后序遍历的顺序是：左子树 -> 右子树 -> 根节点。
• 我们可以递归地对每个非叶子节点的左子树和右子树进行后序遍历，并在遍历到该节点时打印它。

代码实现

Python 实现

def dfs(x, node):
    # 如果当前节点下标超出数组范围，则返回
    if x >= len(node):
        return
    # 遍历左子树
    dfs(2 * x + 1, node)
    # 遍历右子树
    dfs(2 * x + 2, node)
    # 判断当前节点是否为非叶子节点
    if x == 0 or 2 * x + 2 < len(node):
        print(node[x], end=" ")

def main():
    # 输入数据
    node = list(map(int, input().split()))
    # 从根节点开始递归遍历
    dfs(0, node)

if __name__ == "__main__":
    main()

Java 实现

import java.util.Scanner;

public class Main {
    public static void dfs(int x, int[] node) {
        // 如果当前节点下标超出数组范围，则返回
        if (x >= node.length) {
            return;
        }
        // 遍历左子树
        dfs(2 * x + 1, node);
        // 遍历右子树
        dfs(2 * x + 2, node);
        // 判断当前节点是否为非叶子节点
        if (x == 0 || 2 * x + 2 < node.length) {
            System.out.print(node[x] + " ");
        }
    }

    public static void main(String[] args) {
        // 读取输入
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int[] node = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            node[i] = Integer.parseInt(input[i]);
        }
        // 从根节点开始递归遍历
        dfs(0, node);
    }
}

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

void dfs(int x, const vector<int>& node) {
    // 如果当前节点下标超出数组范围，则返回
    if (x >= node.size()) {
        return;
    }
    // 遍历左子树
    dfs(2 * x + 1, node);
    // 遍历右子树
    dfs(2 * x + 2, node);
    // 判断当前节点是否为非叶子节点
    if (x == 0 || 2 * x + 2 < node.size()) {
        cout << node[x] << " ";
    }
}

int main() {
    vector<int> node;
    int val;
    // 读取输入
    while (cin >> val) {
        node.push_back(val);
    }
    // 从根节点开始递归遍历
    dfs(0, node);
    return 0;
}

题目内容

给定一个以顺序储存结构存储整数值的完全二叉树序列（最多1000个整数），请找出此完全二叉树的所有非叶子节点部分，然后采用后序遍历方式将此部分树（不包含叶子）输出。

只有一个节点的树，此节点认定为根节点（非叶子）。

此完全二叉树并非满二叉树，可能存在倒数第二层出现叶子或者无右叶子的情况

其他说明：二叉树的后序遍历是基于根来说的，遍历顺序为：左-右-根

输入描述

一个通过空格分割的整数序列字符串

输出描述

非叶子部分树结构。备注：输出数字以空格分隔

样例1

输入

1 2 3 4 5 6 7

输出

2 3 1

说明

找到非叶子部分树结构，然后采用后序遍历输出。