【C/C++刷题集】二叉树算法题（二）

小年糕是糕手

发布于 2026-01-14 17:33:05

790

文章被收录于专栏：C++学习C++学习

一、二叉树的前序遍历

https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

思路：采用递归的方式，按照“根节点→左子树→右子树”的顺序遍历二叉树并收集节点值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
// 求二叉树结点个数
int BinaryTreeSize(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// 前序遍历
void preOrder(struct TreeNode* root, int* arr, int* pi) {
    if (root == NULL) {
        return;//注意这里不能写return 0这是个void类型的函数
    }
    arr[(*pi)++] = root->val;
    preOrder(root->left, arr, pi);
    preOrder(root->right, arr, pi);
}
//*returnSize:表示要返回的数组的大小
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    // 二叉树结点的个数 = *returnSize
    *returnSize = BinaryTreeSize(root);
    int* arr = (int*)malloc(sizeof(int) * (*returnSize));
    // 前序遍历
    int i = 0;
    preOrder(root, arr, &i);
    return arr;
}

我们根据代码来进一步分析：首先我们看到他给我们preorderTraversal函数，函数的参数有root和returnSize，我们想要去收集二叉树结点的值我们就需要新的空间，而这题没有给我们空间，我们需要自己去malloc，*returnSize就表示返回的数组大小，所以我们要先去写一个函数来求二叉树结点的个数，BinaryTreeSize函数就是用来求结点个数的，相信学到这里大家可以很简单看懂这个函数的应用，然后我们最后再写上一个前序遍历的函数就可以实现了（题二和题三与此题类似，大家可以自行去尝试写，下面俩题我将只给出代码和思路）

二、二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

思路：采用递归的方式，按照“左子树→根节点→右子树”的顺序遍历二叉树并收集节点值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
// 求二叉树的结点个数
int BinaryTreeSize(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// 写出中序遍历的代码
void inOrder(struct TreeNode* root, int* arr, int* pi) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left, arr, pi);
    arr[(*pi)++] = root->val;
    inOrder(root->right, arr, pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    // 用returnSize来接受数组的大小
    *returnSize = BinaryTreeSize(root);
    int* arr = (int*)malloc(sizeof(int )*(*returnSize));
    // 中序遍历
    int i = 0;
    inOrder(root, arr, &i);
    return arr;
}

三、二叉树的后序遍历

https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

思路：采用递归的方式，按照“左子树→右子树→根节点”的顺序遍历二叉树并收集节点值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int BinaryTreeSize(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
void postOrder(struct TreeNode* root, int* arr, int* pi) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left, arr, pi);
    postOrder(root->right, arr, pi);
    arr[(*pi)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = BinaryTreeSize(root);
    int* arr = (int*)malloc(sizeof(int) * (*returnSize));
    // 后序遍历
    int i = 0;
    postOrder(root, arr, &i);
    return arr;
}

四、二叉树的构建及遍历

https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef

思路：先通过先序遍历字符串（含空节点标记）递归构建二叉树，再对构建好的二叉树执行中序遍历（左→根→右）并输出结果。

#include <stdio.h>

//定义二叉树的结构
typedef struct BinaryTreeNode {
    char data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BTNode;

//创建结点
BTNode* buyNode(char x) {
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL) {
        perror("malloc fail!");
        exit(1);
    }

    newnode->data = x;
    newnode->left = newnode->right = NULL;

    return newnode;
}

//构建二叉树
BTNode* createTree(char* arr, int* pi) {
    if (arr[*pi] == '#') {
        (*pi)++;
        return NULL;
    }
    BTNode* root = buyNode(arr[(*pi)++]);
    root->left = createTree(arr, pi);
    root->right = createTree(arr, pi);

    return root;
}

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

int main() {
    //读取输入的字符串保存在数组中
    char arr[100];
    scanf("%s", arr);
    //根据先序遍历创建二叉树
    int i = 0;
    BTNode* root = createTree(arr, &i);
    //中序遍历
    InOrder(root);
    return 0;
}