输出二叉树中从每个叶子结点到根结点的路径代码

好的，以下是输出二叉树中从每个叶子结点到根结点的路径代码：

void printPaths(Node* node) {
    if (node == nullptr) return;

    static vector<int> path;
    path.push_back(node->val);

    if (node->left == nullptr && node->right == nullptr) {
        for (int val : path) {
            cout << val << " ";
        }
        cout << endl;
    } else {
        printPaths(node->left);
        printPaths(node->right);
    }

    path.pop_back();
}

该函数接受一个二叉树的根节点作为参数，并将输出二叉树中从每个叶子结点到根结点的路径。该函数采用递归的方式实现。从根节点开始，当遍历到某个叶子结点时，将该结点到根节点的路径输出，否则递归遍历左子树和右子树。由于要输出所有路径，因此需要保留路径上的结点值，使用一个静态向量 `path` 来存储当前路径。在递归返回的时候，需要将当前结点从 `path` 中弹出，以便处理其他路径。

相关问题

输出二叉树中从每个叶子结点到根结点的路径 C语言代码

以下是输出二叉树中从每个叶子节点到根节点的路径的C语言代码：

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

// 定义二叉树结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 定义栈结构体
struct Stack {
    struct TreeNode **data;   // 存储树节点指针的数组
    int top;    // 栈顶指针
    int size;   // 栈的容量
};

// 初始化栈
struct Stack *stackInit(int size) {
    struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack));
    stack->data = (struct TreeNode **)malloc(size * sizeof(struct TreeNode *));
    stack->top = -1;
    stack->size = size;
    return stack;
}

// 入栈操作
void stackPush(struct Stack *stack, struct TreeNode *node) {
    if (stack->top == stack->size - 1) return;   // 栈满，无法入栈
    stack->top++;
    stack->data[stack->top] = node;
}

// 出栈操作
struct TreeNode *stackPop(struct Stack *stack) {
    if (stack->top == -1) return NULL;   // 栈空，无法出栈
    struct TreeNode *node = stack->data[stack->top];
    stack->top--;
    return node;
}

// 判断栈是否为空
int isStackEmpty(struct Stack *stack) {
    return stack->top == -1;
}

// 判断节点是否为叶子节点
int isLeafNode(struct TreeNode *node) {
    return node && !node->left && !node->right;
}

// 输出路径
void printPath(struct TreeNode **path, int len) {
    for (int i = len - 1; i >= 0; i--) {
        printf("%d", (*path)->val);
        if (i != 0) printf("->");
        (*path) = (*path)->right;
    }
    printf("\n");
}

// 遍历二叉树，输出所有从叶子节点到根节点的路径
void traverse(struct TreeNode *root) {
    if (!root) return;
    struct Stack *stack = stackInit(1000);   // 初始化栈
    struct TreeNode *path[1000];   // 存储从叶子节点到根节点的路径
    int pathLen = 0;   // 路径长度
    struct TreeNode *prev = NULL;   // 记录上一个访问的节点
    stackPush(stack, root);   // 根节点入栈
    while (!isStackEmpty(stack)) {
        struct TreeNode *node = stack->data[stack->top];
        if (!prev || prev->left == node || prev->right == node) {   // 当前节点是上一个节点的子节点
            if (node->left) stackPush(stack, node->left);   // 左子节点入栈
            if (node->right) stackPush(stack, node->right);   // 右子节点入栈
        } else {
            // 当前节点是上一个节点的父节点，且上一个节点为左子节点或当前节点没有右子节点
            if (isLeafNode(prev)) {
                // 上一个节点是叶子节点，输出路径
                path[pathLen++] = prev;
                printPath(path, pathLen);
                pathLen--;
            }
            stackPop(stack);   // 当前节点出栈
        }
        prev = node;   // 更新上一个访问的节点
    }
    free(stack->data);   // 释放动态分配的内存
    free(stack);
}

int main() {
    // 创建二叉树
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->left->val = 4;
    root->left->left->left = NULL;
    root->left->left->right = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->left->val = 5;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->right->val = 6;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    traverse(root);   // 输出所有从叶子节点到根节点的路径

    // 释放动态分配的内存
    free(root->left->left);
    free(root->left);
    free(root->right->left);
    free(root->right->right);
    free(root->right);
    free(root);

    return 0;
}

输出二叉树中从每个叶子结点到根结点的路径

以下是输出二叉树中从每个叶子结点到根结点的路径的 Python 代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def print_all_paths(root: TreeNode):
    def dfs(node, path):
        if not node:
            return
        
        path.append(node.val)
        
        if not node.left and not node.right:
            print(path[::-1])
        else:
            dfs(node.left, path)
            dfs(node.right, path)
        
        path.pop()
    
    dfs(root, [])

这里我们使用深度优先搜索（DFS）遍历整个二叉树，并用一个列表 `path` 记录当前遍历路径上经过的结点值。当遇到叶子结点时，我们将 `path` 列表反转输出，即得到从叶子结点到根结点的路径。

注意在每次遍历完一个结点后，需要将其从 `path` 列表中弹出，以确保下一次遍历从正确的位置开始。