假设二叉树采用二叉链存储结构存储。设计一个算法，输出从每个叶子结点到根结点的逆路径

### 回答1：
算法思路：

1. 从根节点开始遍历二叉树，当遇到叶子节点时，记录下该节点的值，并将其加入到一个栈中。

2. 重复步骤1，直到遍历完整棵树。

3. 从栈中依次取出节点的值，输出即可。

算法实现：

void reversePath(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<int> s;
    reversePathHelper(root, s);
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
}

void reversePathHelper(TreeNode* node, stack<int>& s) {
    if (node == NULL) {
        return;
    }
    if (node->left == NULL && node->right == NULL) {
        s.push(node->val);
        return;
    }
    reversePathHelper(node->left, s);
    reversePathHelper(node->right, s);
    s.push(node->val);
}

其中，`reversePath`函数是主函数，`reversePathHelper`函数是递归函数，用于遍历整棵树并将叶子节点的值加入到栈中。最后，从栈中依次取出节点的值并输出即可。

### 回答2：
二叉树采用二叉链存储结构存储时，每个结点都包含左、右子树的指针和父结点的指针。要输出从每个叶子结点到根结点的逆路径，首先需要遍历二叉树的所有叶子结点。可以采用后序遍历来实现这一操作。在遍历到一个叶子结点时，记录下该结点的父结点指针，并将该结点回溯到根结点。在回溯的过程中，逐个输出经过的结点，直到回溯到根结点。

具体地，可以使用递归算法来实现后序遍历。对于一个结点，先遍历其左子树，再遍历其右子树，最后输出该结点。在遍历到叶子结点时，记录下该结点的父结点指针，并将该结点回溯到根结点。在回溯的过程中，逐个输出经过的结点，直到回溯到根结点。

下面是伪代码实现：

void postOrderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
postOrderTraversal(root->left); // 遍历左子树
postOrderTraversal(root->right); // 遍历右子树
if (root->left == nullptr && root->right == nullptr) { // 遍历到叶子结点
TreeNode* p = root->parent;
while (p != nullptr) { // 回溯到根结点
cout << p->val << " ";
p = p->parent;
}
cout << endl;
}
cout << root->val << " "; // 输出该结点
}

在输出逆路径时，可以采用堆栈来实现。每遍历到一个结点，将其压入堆栈中，并更新指针指向其父结点。在回溯到根结点后，依次弹出堆栈中的结点，即可输出逆路径。

下面是伪代码实现：

void postOrderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
stack<TreeNode*> s;
TreeNode* p = root;
TreeNode* pre = nullptr; // 记录上一次遍历的结点
while (p != nullptr || !s.empty()) {
while (p != nullptr) {
s.push(p);
p = p->left;
}
p = s.top();
if (p->right == nullptr || p->right == pre) { // 已遍历完右子树或右子树为空
if (p->left == nullptr && p->right == nullptr) { // 遍历到叶子结点
TreeNode* q = p;
while (q != nullptr) { // 回溯到根结点
cout << q->val << " ";
q = q->parent;
}
cout << endl;
}
s.pop();
pre = p;
p = nullptr;
} else {
p = p->right;
}
}
}

综上所述，可以使用后序遍历和堆栈来实现输出从每个叶子结点到根结点的逆路径。

### 回答3：
二叉树采用二叉链存储结构，其每个节点有一个左子节点和一个右子节点，因此可以利用递归的方式来实现从每个叶子节点到根节点的逆路径输出。

具体实现步骤如下：

1. 定义一个递归函数，接收一个二叉树节点参数，首先判断该节点是否为空，若为空则返回。

2. 判断当前节点是否为叶子节点，若是，则输出该节点的值，并依次递归输出该节点的父节点，直至根节点。

3. 若当前节点不是叶子节点，则先递归输出它的右子节点的逆路径，再递归输出它的左子节点的逆路径。

4. 在递归结束时，需要判断当前节点是否是根节点，若是，则输出根节点的值。

5. 在主程序中，先判断二叉树是否为空，若为空则直接返回，否则依次遍历二叉树的每个叶子节点，对每个叶子节点都调用递归函数进行逆路径输出。

递归函数的Python实现如下：

def reverse_path(node):
if node is None:
return
if node.left is None and node.right is None:
print(node.value)
while node.parent is not None:
print(node.parent.value)
node = node.parent
return
reverse_path(node.right)
reverse_path(node.left)
if node.parent is None:
print(node.value)

在主程序中，假设二叉树的根节点为root，则可以如下调用reverse_path函数：

def traverse_leaf_to_root(root):
if root is None:
return
if root.left is None and root.right is None:
print(root.value)
return
traverse_leaf_to_root(root.left)
traverse_leaf_to_root(root.right)

# 遍历完所有叶子节点，开始逆路径输出
reverse_path(root)

如此，就可实现从每个叶子节点到根节点的逆路径输出。