【基础数据结构】二叉树的遍历

二叉树的前序遍历

给你二叉树的根节点?root?，返回它节点值的?前序?遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

• 树中节点数目在范围?[0, 100]?内
• -100 <= Node.val <= 100

?官方题解（写的很详细）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/461821/er-cha-shu-de-qian-xu-bian-li-by-leetcode-solution/编译环境Dev-cpp(C++)

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

typedef struct TreeNode {
    int val;  // 节点值
    struct TreeNode* left;  // 左子树指针
    struct TreeNode* right;  // 右子树指针
} TreeNode;

// 前序遍历二叉树的函数
void preorderTraversalHelper(struct TreeNode* root, int* result, int* index) {
    if (root == NULL) {
        return;
    }

    // 访问当前节点
    result[(*index)++] = root->val;

    // 递归遍历左子树
    preorderTraversalHelper(root->left, result, index);

    // 递归遍历右子树
    preorderTraversalHelper(root->right, result, index);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    // 计算二叉树节点个数
    int count = 0;
    struct TreeNode* node = root;
    while (node != NULL) {
        count++;
        node = node->left;
    }

    // 分配存储结果的数组内存
    int* result = (int*)malloc(count * sizeof(int));
    int index = 0;

    // 调用辅助函数进行前序遍历
    preorderTraversalHelper(root, result, &index);

    // 设置返回结果的大小
    *returnSize = index;

    return result;
}

// 创建二叉树节点的函数
struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 构建二叉树的函数
struct TreeNode* buildTree() {
    struct TreeNode* root = createNode(1);
    root->right = createNode(2);
    root->right->left = createNode(3);
    return root;
}

// 释放二叉树节点内存的函数
void freeTree(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    // 构建二叉树
    struct TreeNode* root = buildTree();

    // 前序遍历二叉树
    int returnSize;
    int* result = preorderTraversal(root, &returnSize);

    // 打印结果
    printf("Preorder Traversal: [");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i != returnSize - 1) {
            printf(", ");
        }
    }
    printf("]\n");

    // 释放二叉树节点内存
    freeTree(root);

    // 释放结果数组内存
    free(result);

    return 0;
}

官方题解

方法一：递归

void preorder(struct TreeNode* root, int* res, int* resSize) {
    if (root == NULL) {
        return;
    }
    res[(*resSize)++] = root->val;
    preorder(root->left, res, resSize);
    preorder(root->right, res, resSize);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 2000);
    *returnSize = 0;
    preorder(root, res, returnSize);
    return res;
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/461821/er-cha-shu-de-qian-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：迭代

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 2000);
    *returnSize = 0;
    if (root == NULL) {
        return res;
    }

    struct TreeNode* stk[2000];
    struct TreeNode* node = root;
    int stk_top = 0;
    while (stk_top > 0 || node != NULL) {
        while (node != NULL) {
            res[(*returnSize)++] = node->val;
            stk[stk_top++] = node;
            node = node->left;
        }
        node = stk[--stk_top];
        node = node->right;
    }
    return res;
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/461821/er-cha-shu-de-qian-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

（官方题解的迭代过程有动画更便于理解）

二叉树的中序遍历

给定一个二叉树的根节点?root?，返回?它的?中序?遍历?。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围?[0, 100]?内
• -100 <= Node.val <= 100

?官方题解（有动画）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/编译环境Dev-cpp(C++)

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

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 定义栈结构
struct Stack {
    struct TreeNode** array;
    int size;
    int capacity;
};

// 创建栈
struct Stack* createStack(int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->array = (struct TreeNode**)malloc(capacity * sizeof(struct TreeNode*));
    stack->size = 0;
    stack->capacity = capacity;
    return stack;
}

// 判断栈是否为空
int isEmpty(struct Stack* stack) {
    return stack->size == 0;
}

// 判断栈是否已满
int isFull(struct Stack* stack) {
    return stack->size == stack->capacity;
}

// 入栈
void push(struct Stack* stack, struct TreeNode* item) {
    if (isFull(stack)) {
        return;
    }
    stack->array[stack->size++] = item;
}

// 出栈
struct TreeNode* pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        return NULL;
    }
    return stack->array[--stack->size];
}

// 释放栈内存
void freeStack(struct Stack* stack) {
    free(stack->array);
    free(stack);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    // 创建结果数组和栈
    int* result = (int*)malloc(100 * sizeof(int));
    struct Stack* stack = createStack(100);
    int index = 0;

    // 中序遍历
    struct TreeNode* current = root;
    while (current != NULL || !isEmpty(stack)) {
        // 将左子树的所有节点入栈
        while (current != NULL) {
            push(stack, current);
            current = current->left;
        }

        // 弹出栈顶节点并添加到结果数组
        current = pop(stack);
        result[index++] = current->val;

        // 处理右子树
        current = current->right;
    }

    // 设置返回结果的大小
    *returnSize = index;

    // 释放栈内存
    freeStack(stack);

    return result;
}

// 创建二叉树节点的函数
struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 构建二叉树的函数
struct TreeNode* buildTree() {
    struct TreeNode* root = createNode(1);
    root->right = createNode(2);
    root->right->left = createNode(3);
    return root;
}

// 释放二叉树节点内存的函数
void freeTree(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    // 构建二叉树
    struct TreeNode* root = buildTree();

    // 中序遍历
    int returnSize = 0;
    int* result = inorderTraversal(root, &returnSize);

    // 打印结果
    printf("Inorder Traversal: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    // 释放二叉树节点内存
    freeTree(root);

    // 释放结果数组内存
    free(result);

    return 0;
}

官方题解

方法一：递归

void inorder(struct TreeNode* root, int* res, int* resSize) {
    if (!root) {
        return;
    }
    inorder(root->left, res, resSize);
    res[(*resSize)++] = root->val;
    inorder(root->right, res, resSize);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 501);
    *returnSize = 0;
    inorder(root, res, returnSize);
    return res;
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/412886/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

?方法二：迭代

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    int* res = malloc(sizeof(int) * 501);
    struct TreeNode** stk = malloc(sizeof(struct TreeNode*) * 501);
    int top = 0;
    while (root != NULL || top > 0) {
        while (root != NULL) {
            stk[top++] = root;
            root = root->left;
        }
        root = stk[--top];
        res[(*returnSize)++] = root->val;
        root = root->right;
    }
    return res;
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/412886/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二叉树的后序遍历

给你一棵二叉树的根节点?root?，返回其节点值的?后序遍历?。

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点的数目在范围?[0, 100]?内
• -100 <= Node.val <= 100

官方题解（有动画）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/binary-tree-postorder-traversal/solutions/431066/er-cha-shu-de-hou-xu-bian-li-by-leetcode-solution/?编译环境Dev-cpp(C++)

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

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 定义栈结构
struct Stack {
    struct TreeNode** array;
    int size;
    int capacity;
};

// 创建栈
struct Stack* createStack(int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->array = (struct TreeNode**)malloc(capacity * sizeof(struct TreeNode*));
    stack->size = 0;
    stack->capacity = capacity;
    return stack;
}

// 判断栈是否为空
int isEmpty(struct Stack* stack) {
    return stack->size == 0;
}

// 判断栈是否已满
int isFull(struct Stack* stack) {
    return stack->size == stack->capacity;
}

// 入栈
void push(struct Stack* stack, struct TreeNode* item) {
    if (isFull(stack)) {
        return;
    }
    stack->array[stack->size++] = item;
}

// 出栈
struct TreeNode* pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        return NULL;
    }
    return stack->array[--stack->size];
}

// 释放栈内存
void freeStack(struct Stack* stack) {
    free(stack->array);
    free(stack);
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    // 创建结果数组和栈
    int* result = (int*)malloc(100 * sizeof(int));
    struct Stack* stack = createStack(100);
    int index = 0;

    // 定义前一个访问的节点
    struct TreeNode* prev = NULL;

    // 后序遍历
    while (root != NULL || !isEmpty(stack)) {
        // 将当前节点及其左子树的所有节点入栈
        while (root != NULL) {
            push(stack, root);
            root = root->left;
        }

        // 检查栈顶节点的右子树
        struct TreeNode* top = stack->array[stack->size - 1];

        // 如果栈顶节点的右子树为空或已经被访问过，则可以访问栈顶节点
        if (top->right == NULL || top->right == prev) {
            result[index++] = top->val;
            prev = top;
            pop(stack);
        } else {
            // 否则，将栈顶节点的右子树作为当前节点继续遍历
            root = top->right;
        }
    }

    // 设置返回结果的大小
    *returnSize = index;

    // 释放栈内存
    freeStack(stack);

    return result;
}

// 创建二叉树节点的函数
struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 构建二叉树的函数
struct TreeNode* buildTree() {
    struct TreeNode* root = createNode(1);
    root->right = createNode(2);
    root->right->left = createNode(3);
    return root;
}

// 释放二叉树节点内存的函数
void freeTree(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    // 构建二叉树
    struct TreeNode* root = buildTree();

    // 后序遍历
    int returnSize = 0;
    int* result = postorderTraversal(root, &returnSize);

    // 打印结果
    printf("Postorder Traversal: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    // 释放二叉树节点内存
    freeTree(root);

    // 释放结果数组内存
    free(result);

    return 0;
}

官方题解

方法一：递归

void postorder(struct TreeNode *root, int *res, int *resSize) {
    if (root == NULL) {
        return;
    }
    postorder(root->left, res, resSize);
    postorder(root->right, res, resSize);
    res[(*resSize)++] = root->val;
}

int *postorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = malloc(sizeof(int) * 2001);
    *returnSize = 0;
    postorder(root, res, returnSize);
    return res;
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/solutions/431066/er-cha-shu-de-hou-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：迭代

int *postorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = malloc(sizeof(int) * 2001);
    *returnSize = 0;
    if (root == NULL) {
        return res;
    }
    struct TreeNode **stk = malloc(sizeof(struct TreeNode *) * 2001);
    int top = 0;
    struct TreeNode *prev = NULL;
    while (root != NULL || top > 0) {
        while (root != NULL) {
            stk[top++] = root;
            root = root->left;
        }
        root = stk[--top];
        if (root->right == NULL || root->right == prev) {
            res[(*returnSize)++] = root->val;
            prev = root;
            root = NULL;
        } else {
            stk[top++] = root;
            root = root->right;
        }
    }
    return res;
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/solutions/431066/er-cha-shu-de-hou-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二叉树的层序遍历

给你二叉树的根节点?root?，返回其节点值的?层序遍历?。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围?[0, 2000]?内
• -1000 <= Node.val <= 1000

?大佬题解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int** ans=(int**)malloc(sizeof(int*)*2000);
    *returnSize=0;
    if(!root) return NULL;//要在return前给出*returnSize的取值不然过不去；！！
    int columnSizes[2000];//记录每一行的列数（每层结点数），因为要给出* returnColumnSizes
    struct TreeNode* queue[2000];//模拟队列
    int rear=0;int head=0;//记录队列头尾
    queue[rear++]=root;//录入根结点

    while(rear!=head){//队列不为空
        ans[(*returnSize)]=(int*)malloc(sizeof(int)*(rear-head));
        columnSizes[(*returnSize)]=rear-head;
        int start=head;//记录遍历开始位置，即为本层的头
        head=rear;//本层的尾部成为下次的头，因为所有的元素均弹出队列
        //在这里下层的头head同时作为遍历结束的位置，因为在遍历中rear会不断改变，成为下层的尾
        for(int i=start;i<head;i++){//弹出start到未变化的rear（即为head）之间的所有元素
            ans[(*returnSize)][i-start]=queue[i]->val;
            if(queue[i]->left) queue[rear++]=queue[i]->left;
            if(queue[i]->right) queue[rear++]=queue[i]->right;//rear不断改变
        }
        (*returnSize)++;//一层遍历完*returnSize加一；
       
    }
    *returnColumnSizes=(int*)malloc(sizeof(int)*(*returnSize));//给出*returnColumnSizes
    for(int i=0;i<*returnSize;i++) (*returnColumnSizes)[i]=columnSizes[i];
    return ans;
}

作者：我不是朝伟
链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/2149734/er-cha-shu-de-ceng-xu-bian-li-chun-cwu-x-c8yq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

优先搜索

给你二叉树的根节点?root?和一个整数目标和?targetSum?，找出所有?从根节点到叶子节点?路径总和等于给定目标和的路径。

叶子节点?是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

提示：

• 树中节点总数在范围?[0, 5000]?内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

官方题解

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/path-sum-ii/solutions/427759/lu-jing-zong-he-ii-by-leetcode-solution/?方法一：深度优先搜索

int** ret;
int retSize;
int* retColSize;

int* path;
int pathSize;

void dfs(struct TreeNode* root, int targetSum) {
    if (root == NULL) {
        return;
    }
    path[pathSize++] = root->val;
    targetSum -= root->val;
    if (root->left == NULL && root->right == NULL && targetSum == 0) {
        int* tmp = malloc(sizeof(int) * pathSize);
        memcpy(tmp, path, sizeof(int) * pathSize);
        ret[retSize] = tmp;
        retColSize[retSize++] = pathSize;
    }
    dfs(root->left, targetSum);
    dfs(root->right, targetSum);
    pathSize--;
}

int** pathSum(struct TreeNode* root, int targetSum, int* returnSize, int** returnColumnSizes) {
    ret = malloc(sizeof(int*) * 2001);
    retColSize = malloc(sizeof(int) * 2001);
    path = malloc(sizeof(int) * 2001);
    retSize = pathSize = 0;
    dfs(root, targetSum);
    *returnColumnSizes = retColSize;
    *returnSize = retSize;
    return ret;
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/path-sum-ii/solutions/427759/lu-jing-zong-he-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：广度优先搜索

int** ret;
int retSize;
int* retColSize;

int* path;
int pathSize;

typedef struct {
    struct TreeNode* key;
    struct TreeNode* val;
    UT_hash_handle hh;
} hashTable;

hashTable* parent;

void insertHashTable(struct TreeNode* x, struct TreeNode* y) {
    hashTable* rec = malloc(sizeof(hashTable));
    rec->key = x;
    rec->val = y;
    HASH_ADD_PTR(parent, key, rec);
}

struct TreeNode* queryHashTable(struct TreeNode* x) {
    hashTable* rec;
    HASH_FIND_PTR(parent, &x, rec);
    return rec->val;
}

void getPath(struct TreeNode* node) {
    int* tmp = malloc(sizeof(int) * 2001);
    int tmpSize = 0;
    while (node != NULL) {
        tmp[tmpSize++] = node->val;
        node = queryHashTable(node);
    }
    for (int i = 0; i < tmpSize / 2; i++) {
        int t = tmp[i];
        tmp[i] = tmp[tmpSize - 1 - i], tmp[tmpSize - 1 - i] = t;
    }
    ret[retSize] = tmp;
    retColSize[retSize++] = tmpSize;
}

int** pathSum(struct TreeNode* root, int targetSum, int* returnSize, int** returnColumnSizes) {
    ret = malloc(sizeof(int*) * 2001);
    retColSize = malloc(sizeof(int) * 2001);
    path = malloc(sizeof(int) * 2001);
    retSize = pathSize = 0;
    parent = NULL;
    insertHashTable(root, NULL);

    if (root == NULL) {
        *returnColumnSizes = retColSize;
        *returnSize = retSize;
        return ret;
    }

    struct TreeNode* que_node[10001];
    int que_sum[10001];
    int left = 0, right = 0;
    que_node[right] = root;
    que_sum[right++] = 0;

    while (left < right) {
        struct TreeNode* node = que_node[left];
        int rec = que_sum[left++] + node->val;
        if (node->left == NULL && node->right == NULL) {
            if (rec == targetSum) {
                getPath(node);
            }
        } else {
            if (node->left != NULL) {
                insertHashTable(node->left, node);
                que_node[right] = node->left;
                que_sum[right++] = rec;
            }
            if (node->right != NULL) {
                insertHashTable(node->right, node);
                que_node[right] = node->right;
                que_sum[right++] = rec;
            }
        }
    }

    *returnColumnSizes = retColSize;
    *returnSize = retSize;
    return ret;
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/path-sum-ii/solutions/427759/lu-jing-zong-he-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。