题解 | #二叉树的前，中，后序遍历#（递归）

前，中，后遍历的思路相同

代码如下：

C++版本

前序遍历

class Solution {
public:
    vector<int> res;
    void dfs(TreeNode* Node){
        if(Node == nullptr) return;
        res.push_back(Node->val);
        dfs(Node->left);
        dfs(Node->right);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        dfs(root);
        return res;
    }
};

中序遍历

class Solution {
public:
    vector<int> res;
    void dfs(TreeNode* Node){
        if(Node == nullptr) return;
        dfs(Node->left);
        res.push_back(Node->val);
        dfs(Node->right);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        dfs(root);
        return res;
    }
};

后序遍历

class Solution {
public:
    vector<int> res;
    void dfs(TreeNode* Node){
        if(Node == nullptr) return;
        dfs(Node->left);
        dfs(Node->right);
        res.push_back(Node->val);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        dfs(root);
        return res;
    }
};

C语言版本

前序遍历

void preOrderTraversal(struct TreeNode* node, int* ret, int* returnSize) {
    if(!node) return;
    ret[(*returnSize)++] = node->val;
    preOrderTraversal(node->left, ret, returnSize);
    preOrderTraversal(node->right, ret, returnSize);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    preOrderTraversal(root, ret, returnSize);
    return ret;
}

中序遍历

void inOrder(struct TreeNode* node, int* ret, int* returnSize) {
    if(!node) return;
    inOrder(node->left, ret, returnSize);
    ret[(*returnSize)++] = node->val;
    inOrder(node->right, ret, returnSize);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    inOrder(root, ret, returnSize);
    return ret;
}

后序遍历

void postOrder(struct TreeNode* node, int* ret, int* returnSize) {
    if(!node) return;
    postOrder(node->left, ret, returnSize);
    postOrder(node->right, ret, returnSize);
    ret[(*returnSize)++] = node->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret= (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    postOrder(root, ret, returnSize);
    return ret;
}