后序遍历递归算法

二叉树是一种常用的数据结构，其中每个节点最多有两个子节点，左子节点和右子节点。在对二叉树进行遍历时，按节点访问顺序可以分为前序遍历、中序遍历和后序遍历。对于后序遍历，一般使用递归算法实现。

后序遍历是指先访问左子树，然后访问右子树，最后访问根节点的遍历方式。具体实现时，可以先递归遍历左子树，再递归遍历右子树，最后访问根节点。下面以一个例子来说明后序遍历递归算法的具体实现过程。

假设有如下二叉树：

```

1

/ \

2 3

/ \

4 5

```

按照后序遍历的顺序，先访问左子树，即访问节点4和5，然后访问右子树，即访问节点2和3，最后访问根节点1。因此，后序遍历二叉树的结果为4 5 2 3 1。

下面给出后序遍历二叉树的递归算法实现方式：

```

void postorderTraversal(TreeNode *root) {

if (root) {

postorderTraversal(root->left); // 遍历左子树

postorderTraversal(root->right); // 遍历右子树

printf("%d ", root->val); // 访问根节点

}

}

```

在这个递归函数中，首先判断当前节点是否为空，如果不为空则递归访问左子树和右子树，最后访问根节点。这种实现方式简单易懂，但存在一个问题：递归过程中可能会导致栈溢出，因为递归过程中会不断向栈中压入新的函数调用，当递归深度较大时，栈可能会被耗尽。因此，采用非递归算法实现后序遍历是更好的选择。

具体实现时，可以使用一个栈来保存节点，先将根节点和其左子节点依次入栈，然后不断弹出栈顶元素，如果它没有右子节点或其右子节点已经被访问过，则访问该节点；否则，将该节点右子节点和其自身重新入栈。这样，最后访问的序列即为后序遍历结果。下面给出非递归实现的代码：

```

vector postorderTraversal(TreeNode* root) {

vector res;

if (!root) return res;

stack s{{root}};

TreeNode* head = root;

while (!s.empty()) {

TreeNode* t = s.top();

if ((!t->left && !t->right) || t->left == head || t->right == head) {

res.push_back(t->val);

s.pop();

head = t;

} else {

if (t->right) s.push(t->right);

if (t->left) s.push(t->left);

}

}

return res;

}

```

这个算法的时间复杂度为O(n)，空间复杂度为O(n)，因为需要使用一个栈来保存节点。

综上所述，后序遍历递归算法是对二叉树进行后序遍历的一种简单实现方式，但存在栈溢出和效率低下的问题。因此，采用非递归算法实现后序遍历是更好的选择。