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

二叉树的前序遍历问题分析及解决方案

项目场景

我们需要实现一个函数，该函数接受二叉树的根节点，并返回其节点值的前序遍历结果。

问题描述

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

原因分析

解决方案

递归算法

/** * 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(). */#define SIZE 2000void 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) * SIZE);    *returnSize = 0;    preorder(root, res, returnSize);    return res;}

非递归实现

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;}

总结

通过递归和非递归两种方法，我们可以高效地实现二叉树的前序遍历。递归方法直观简洁，而非递归方法在栈溢出风险较低的情况下提供了另一种实现方案。选择哪种方法取决于具体需求和性能考量。