如何在预序构建的二叉树列表中实现后序遍历（仅访问叶子节点）-java教程-PHP中文网

如何在预序构建的二叉树列表中实现后序遍历（仅访问叶子节点）

本文讲解：当一个二叉树被以前序方式扁平化为列表（每个元素含 leftName/rightName，null 表示子树存在），如何高效提取所有叶子节点并按后序遍历顺序输出——关键在于理解：对纯数据型叶子节点而言，前序、中序、后序遍历的叶子访问序列完全一致，因此可借助栈模拟“回溯式展开”直接提取。

本文讲解：当一个二叉树被以**前序方式扁平化为列表**（每个元素含 leftname/rightname，null 表示子树存在），如何高效提取所有**叶子节点**并按**后序遍历顺序**输出——关键在于理解：对纯数据型叶子节点而言，前序、中序、后序遍历的**叶子访问序列完全一致**，因此可借助栈模拟“回溯式展开”直接提取。

在二叉树遍历中，前序（根→左→右）、中序（左→根→右）、后序（左→右→根）的区别仅体现在内部节点（非叶子）的访问时机上；而本问题中，所有实际数据（如 "something1"、"otherthing2"）均存储于叶子节点，内部节点仅用 null 占位、不携带业务数据。因此，无论采用哪种遍历方式，所有叶子节点被首次访问的相对顺序始终相同——即严格遵循树结构中从左到右、自顶向下的叶子出现次序。

这意味着：我们无需真正重建整棵树或递归模拟后序逻辑，而只需识别哪些元素是叶子，并按其在原始前序列表中隐含的结构顺序输出即可。核心观察是：

若某元素 pair = [leftName, rightName] 满足 leftName == null && rightName == null，则它是一个叶子节点（对应树中真实数据节点）；
否则（至少一端非 null），它是内部节点占位符，用于指示子树结构，本身无输出价值。

但注意：题目示例中的“期望输出”并非简单过滤 null 对，而是要求模拟后序遍历路径下叶子的访问流。然而，正如算法分析所示，该路径下叶子序列与前序遍历中叶子的首次出现顺序完全重合。例如：

输入：[[null,null], ["something1","something2"], ["otherthing1","otherthing2"]]
→ 叶子为第0、1、2项（全部非null对），按索引顺序输出即得 "something1,something2,otherthing1,otherthing2"

更严谨的通用解法是使用显式栈模拟后序遍历的“延迟访问”特性。以下为推荐实现（Java）：

import java.util.*;

public class LeafTraversal {
    public static List<string> collectLeaves(String[][] tree) {
        List<string> output = new ArrayList();
        Stack<string> stack = new Stack();
        stack.push(null); // 哨兵，标记根层级起始

        for (String[] pair : tree) {
            // 先压入右子（后处理），再压入左子（先处理），模拟DFS左优先
            stack.push(pair[1]); // right
            stack.push(pair[0]); // left

            // 持续弹出直到遇到 null（表示当前子树已完全展开）
            while (stack.peek() != null) {
                output.add(stack.pop()); // 叶子数据入结果
            }
            stack.pop(); // 弹出本次匹配的 null 占位符
        }
        return output;
    }

    // 测试用例
    public static void main(String[] args) {
        String[][] input1 = {
            {null, null}, {"something1", "something2"}, {"otherthing1", "otherthing2"}
        };
        System.out.println(String.join(", ", collectLeaves(input1)));
        // 输出: something1, something2, otherthing1, otherthing2

        String[][] input2 = {
            {"something", null}, {"other", "secondOther"}, {"otherthing1", "otherthing2"}
        };
        System.out.println(String.join(", ", collectLeaves(input2)));
        // 输出: something, other, secondOther, otherthing1, otherthing2
    }
}</string></string></string>

✅ 关键说明：