设计算法，输出二叉树中从每个叶子结点到根结点的路径

可以使用深度优先搜索(DFS)来遍历二叉树，并且在每个叶子节点处记录路径。具体步骤如下：

1. 定义一个栈，用于存储结点，将根结点入栈。
2. 定义一个哈希表用于存储每个叶子节点的路径，初始为空。
3. 当栈不为空时，取出栈顶结点。
4. 如果该结点是叶子节点，则记录该结点路径(从该叶子节点到根节点的路径为从哈希表中该叶子节点的路径倒序连接上该叶子节点的值和"/")。
5. 否则，将该结点的右子节点和左子节点分别入栈。
6. 重复步骤3-5直至栈为空。

最后，输出哈希表中记录的所有路径即可。

相关问题

C语言编写代码：1．以二叉链表表示二叉树，建立一棵二叉树（算法 5.3）； 2．输出二叉树的中序遍历结果（算法 5.1）； 3．输出二叉树的前序遍历结果（见讲稿）； 4．输出二叉树的后序遍历结果（见讲稿）； 5．计算二叉树的深度（算法 5.5）； 6．统计二叉树的结点个数（算法 5.6）； 7．统计二叉树的叶结点个数； 8．统计二叉树的度为 1 的结点个数； 9．输出二叉树中从每个叶子结点到根结点的路径。10.交换二叉树每个结点的左孩子和右孩子； 11.设计二叉树的双序遍历(DblOrderTraverse)算法

以下是C语言代码实现：

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

// 定义二叉树结点结构体
typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建二叉树
TreeNode *create_tree() {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        return NULL;
    }
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->data = ch;
    node->left = create_tree();
    node->right = create_tree();
    return node;
}

// 中序遍历
void inorder_traverse(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorder_traverse(root->left);
    printf("%c ", root->data);
    inorder_traverse(root->right);
}

// 前序遍历
void preorder_traverse(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    preorder_traverse(root->left);
    preorder_traverse(root->right);
}

// 后序遍历
void postorder_traverse(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    postorder_traverse(root->left);
    postorder_traverse(root->right);
    printf("%c ", root->data);
}

// 计算二叉树深度
int get_depth(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int left_depth = get_depth(root->left);
    int right_depth = get_depth(root->right);
    return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}

// 统计二叉树结点个数
int count_nodes(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + count_nodes(root->left) + count_nodes(root->right);
}

// 统计二叉树叶结点个数
int count_leaf_nodes(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return count_leaf_nodes(root->left) + count_leaf_nodes(root->right);
}

// 统计二叉树度为 1 的结点个数
int count_degree_one_nodes(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int degree = 0;
    if (root->left != NULL) {
        degree++;
    }
    if (root->right != NULL) {
        degree++;
    }
    if (degree == 1) {
        return 1 + count_degree_one_nodes(root->left) + count_degree_one_nodes(root->right);
    } else {
        return count_degree_one_nodes(root->left) + count_degree_one_nodes(root->right);
    }
}

// 输出二叉树中从每个叶子结点到根结点的路径
void print_leaf_to_root_path(TreeNode *root, int path[], int path_len) {
    if (root == NULL) {
        return;
    }
    path[path_len] = root->data;
    path_len++;
    if (root->left == NULL && root->right == NULL) {
        printf("Path: ");
        for (int i = path_len - 1; i >= 0; i--) {
            printf("%c ", path[i]);
        }
        printf("\n");
    } else {
        print_leaf_to_root_path(root->left, path, path_len);
        print_leaf_to_root_path(root->right, path, path_len);
    }
}

// 交换二叉树每个结点的左孩子和右孩子
void swap_children(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    TreeNode *temp = root->left;
    root->left = root->right;
    root->right = temp;
    swap_children(root->left);
    swap_children(root->right);
}

// 双序遍历
void dbl_order_traverse(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    if (root->left != NULL) {
        dbl_order_traverse(root->left);
        printf("%c ", root->data);
    }
    if (root->right != NULL) {
        dbl_order_traverse(root->right);
        printf("%c ", root->data);
    }
}

int main() {
    // 创建二叉树
    printf("请输入二叉树，用 # 表示空结点：\n");
    TreeNode *root = create_tree();

    // 中序遍历
    printf("中序遍历结果：\n");
    inorder_traverse(root);
    printf("\n");

    // 前序遍历
    printf("前序遍历结果：\n");
    preorder_traverse(root);
    printf("\n");

    // 后序遍历
    printf("后序遍历结果：\n");
    postorder_traverse(root);
    printf("\n");

    // 计算二叉树深度
    printf("二叉树深度为：%d\n", get_depth(root));

    // 统计二叉树结点个数
    printf("二叉树结点个数为：%d\n", count_nodes(root));

    // 统计二叉树叶结点个数
    printf("二叉树叶结点个数为：%d\n", count_leaf_nodes(root));

    // 统计二叉树度为 1 的结点个数
    printf("二叉树度为 1 的结点个数为：%d\n", count_degree_one_nodes(root));

    // 输出二叉树中从每个叶子结点到根结点的路径
    int path[100];
    printf("从每个叶子结点到根结点的路径：\n");
    print_leaf_to_root_path(root, path, 0);

    // 交换二叉树每个结点的左孩子和右孩子
    swap_children(root);
    printf("交换左右孩子后的前序遍历结果：\n");
    preorder_traverse(root);
    printf("\n");

    // 双序遍历
    printf("双序遍历结果：\n");
    dbl_order_traverse(root);
    printf("\n");

    return 0;
}

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

### 回答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)

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