[C++知识库]二叉树的后序遍历【C和C++】

二叉树的后续遍历就是根结点在最后遍历，顺序是左--右--根，如下图所示，先遍历左子树，1没有左结点，所以直接遍历右子树。看到右子树后，2是根结点，遍历它的左子树，返回3，因为2没有右子树，所以返回2，最后返回1。

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

输出：[3,2,1]

树的结点定义如下：

?struct?TreeNode?{

?? ? ?int?val;

?? ? ?struct?TreeNode?*left;

?? ? ?struct?TreeNode?*right;

??};

?递归的C语言代码如下：

void postorder(struct TreeNode* root, int* res, int* size){
    if(root == NULL)  return;  //当递归到根节点为空时，说明已经到了叶节点的子结点，直接返回
    postorder(root->left, res, size);  //递归左子树
    postorder(root->right, res, size);  //递归右子树
    res[(*size)++] = root->val;  //将根结点的值保存在res中
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* res = malloc(sizeof(int) * 2000);  //res是结点返回的序列，这里先为res创建空间
    *returnSize = 0;
    postorder(root, res, returnSize);
    return res;
}

递归的C++代码如下：

class Solution {
public:
    void postorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }  //当递归到根节点为空时，说明已经到了叶节点的子结点，直接返回
        postorder(root->left, res);  //递归左子树
        postorder(root->right, res);  //递归右子树
        res.push_back(root->val);  //将根结点的值保存在res中
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;  //创建容器res存放结点的值
        postorder(root, res);
        return res;
    }
};

用递归法来解决二叉树的中序遍历的空间复杂度是O（n），空间复杂度取决于递归的栈深度，当二叉树是一条链的时候栈的深度会达到O（n）；时间复杂度也是O（n），这是很好理解的，因为每个结点都遍历了一遍且只遍历一遍。