27.完全二叉树非叶子部分后序遍历（递归 + 迭代双解法）

📚 题目描述

📝 核心要求

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

📝 特殊规则

1. 只有一个节点的树，此节点认定为根节点（非叶子）。
2. 此完全二叉树并非满二叉树，可能存在倒数第二层出现叶子或者无右叶子的情况。
3. 后序遍历顺序：左子树 → 右子树 → 根节点。

📝 输入输出描述

输入 一个通过空格分割的整数序列字符串 输出 非叶子节点的后序遍历结果

📝 示例说明

示例 1

• 输入：1 2 3 4 5 6 7 • 输出：2 3 1 • 解释：非叶子节点为 1、2、3，后序遍历顺序为 2 → 3 → 1

示例 2

• 输入：1 • 输出：1 • 解释：单个节点认定为非叶子节点

💡 解题思路

📝 核心知识点

1. 完全二叉树顺序存储特性（数组下标从 0 开始）：

◦ 节点i的左孩子下标：2*i+1
◦ 节点i的右孩子下标：2*i+2

2. 非叶子节点判断规则：

◦ 只要节点的左孩子下标小于数组长度，该节点即为非叶子节点

3. 后序遍历实现思路：

◦ 递归法：遵循「左→右→根」的递归遍历逻辑，仅处理非叶子节点
◦ 迭代法：利用栈的 LIFO 特性，先压入根节点，再依次压入左 / 右子节点，最后反转输出

🔧 代码实现

📝 方法一：递归实现（RecursiveTraversal）

package com.study.algorithm.HuaweiOD.完全二叉树非叶子部分后序遍历; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * 递归法实现完全二叉树非叶子节点后序遍历 * 核心逻辑：递归遍历左子树 → 递归遍历右子树 → 处理当前非叶子节点 * @author Tony_Yi * @version 1.0 * @date 2026/02/24 */ public class RecursiveTraversal { // 全局列表，存储非叶子节点的后序遍历结果 static List<Integer> result = new ArrayList