本文共 2392 字，大约阅读时间需要 7 分钟。

二叉树的前序、中序、后序遍历实现

给定二叉树的根节点 root，返回它的前序、中序、后序遍历结果。

前序遍历（Preorder Traversal）

前序遍历的特点是先访问根节点，再访问左子树，最后访问右子树。

实现步骤

代码示例

int GetSize(struct TreeNode* root) {
    if (root == NULL) return 0;
    return GetSize(root->left) + GetSize(root->right) + 1;
}
void Traversal(int* arr, struct TreeNode* root, int* count) {
    if (root != NULL) {
        arr[*count] = root->val;
        (*count)++;
        Traversal(arr, root->left, count);
        Traversal(arr, root->right, count);
    }
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int size = GetSize(root);
    int* arr = (int*)malloc(sizeof(int) * size);
    int count = 0;
    Traversal(arr, root, &count);
    *returnSize = count;
    return arr;
}

中序遍历（Inorder Traversal）

中序遍历的特点是先访问左子树，最后访问右子树，根节点值最后一个访问。

实现步骤

代码示例

int GetSize(struct TreeNode* root) {
    if (root == NULL) return 0;
    return GetSize(root->left) + GetSize(root->right) + 1;
}
void Traversal(int* arr, struct TreeNode* root, int* count) {
    if (root) {
        Traversal(arr, root->left, count);
        arr[(*count)++] = root->val;
        Traversal(arr, root->right, count);
    }
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int size = GetSize(root);
    int* arr = (int*)malloc(sizeof(int) * size);
    int count = 0;
    Traversal(arr, root, &count);
    *returnSize = count;
    return arr;
}

后序遍历（Postorder Traversal）

后序遍历的特点是先访问左子树和右子树，最后访问根节点。

实现步骤

代码示例

int GetSize(struct TreeNode* root) {
    if (root == NULL) return 0;
    return GetSize(root->left) + GetSize(root->right) + 1;
}
void Traversal(int* arr, struct TreeNode* root, int* count) {
    if (root) {
        Traversal(arr, root->left, count);
        Traversal(arr, root->right, count);
        arr[(*count)++] = root->val;
    }
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int size = GetSize(root);
    int* arr = (int*)malloc(sizeof(int) * size);
    int count = 0;
    Traversal(arr, root, &count);
    *returnSize = count;
    return arr;
}

总结

这三种遍历方法虽然实现方式不同，但核心思想都是通过递归的方式遍历树节点，区别仅在于访问顺序的不同。通过合理设计递归函数和存储数组，可以轻松实现任意顺序的遍历。