我在网上冲浪的时候，看到一个有趣的帖子。有个同学在理想汽车面试，面试的时候，他们聊到了二叉树的后序遍历。

同学信心满满地说后序遍历是“左-中-右”，结果面试官一本正经地反驳说不是。这下好了，把那同学给整懵逼了。


来，给大家普及下知识点，二叉树的后序遍历其实就是“左-右-中”。但这面试官，不知是故意的还是怎样，这么一整，直接让人摸不着头脑。

网友也是各种评论调侃整花活，哈哈。


所以啊，面试有时候不仅仅是考察你的技术能力，更是一场心理游戏。

正好今天提到了二叉树的后序遍历，而且这个算法确实是很重要，那么今天的算法题我们就来看一看这二叉树的后序遍历。

下面是算法题

今日算法题，来自LeetCode的第145题：二叉树的后序遍历，下面是我的算法思路及实现，让我们来看看吧。

算法题目

给定一个二叉树，返回它的后序遍历结果。

算法思路

递归法
递归遍历左子树
递归遍历右子树
访问根节点

迭代法

使用栈模拟递归过程：

创建一个栈来存储节点，以及一个用于存储结果的列表。
迭代处理：将根节点入栈，然后迭代执行以下操作，直到栈为空：
弹出栈顶元素，将其值添加到结果列表的前面（这是为了保证访问顺序为左、右、根）。
先将左子节点入栈，然后是右子节点（这样可以保证右子节点先被处理）。
代码实现

C语言实现(递归)
#include <stdio.h>#include <stdlib.h>
typedef struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;} TreeNode;
void postorderTraversalRec(TreeNode* root, int* returnSize, int* result) {    if (root == NULL) return;    postorderTraversalRec(root->left, returnSize, result);    postorderTraversalRec(root->right, returnSize, result);    result[(*returnSize)++] = root->val;}
int* postorderTraversal(TreeNode* root, int* returnSize) {    *returnSize = 0;    int* result = (int*)malloc(sizeof(int) * 100); // Assuming max 100 nodes    postorderTraversalRec(root, returnSize, result);    return result;}

Java实现(迭代)
import java.util.*;
public class TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int x) { val = x; }}
class Solution {    public List<Integer> postorderTraversal(TreeNode root) {        LinkedList<Integer> ans = new LinkedList<>();        Stack<TreeNode> stack = new Stack<>();        if (root == null) return ans;
        stack.push(root);        while (!stack.isEmpty()) {            TreeNode cur = stack.pop();            ans.addFirst(cur.val);            if (cur.left != null) stack.push(cur.left);            if (cur.right != null) stack.push(cur.right);        }        return ans;    }}
‍

Python实现(递归)
class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = right
def postorderTraversal(root: TreeNode) -> [int]:    def recur(node):        if not node:            return        recur(node.left)        recur(node.right)        result.append(node.val)        result = []    recur(root)    return result

算法解析

后序遍历的实现主要有两种方式：递归和迭代。递归实现比较直观，但迭代实现可以提供更好的空间效率。无论哪种方式，核心思想都是遵循左子树、右子树、根节点的访问顺序。

示例和测试

假设有一个二叉树如下：
  1    \    2    /  3
后序遍历的结果应该是 [3,2,1]。

总结

二叉树的后序遍历是基础且重要的算法，掌握其递归和迭代两种实现方式对深入理解树结构和相关算法非常有帮助。
大家好，我是鬼哥，我们团队自主研发的AI项目在2023年成都市重庆市联合举办的《创新创业大赛》中荣获二等奖，获得专家团队一致好评！

2023年可以说是AI爆发的一年，AI的强大已经足以颠覆我们的工作和生活，如果以前是互联网+，那么现在及未来就是AI+，所以你已经在通过AI来赋能了吗？

说真的AI带给我们的冲击太大，我们深刻的感知到：未来淘汰你的不一定是AI，但一定是会使用AI的人。

在不远的未来，AI必然代替人类大部分的工作。打败你的不是对手，颠覆你的不是同行！

我和我的团队，打造了这门关于AI的实操课程带你从小白成为ChatGPT专家，10倍提升业务生产力。

现在买教程立即送ChatGPT独立账号，支持修改密码，无需等待！

扫描下方二维码，购买《AI实战课程》，送ChatGPT独享账号！


推荐阅读：
Sora发布时间确定！OpenAI的首席技术官透露细节
12.4k Star！一键修复人脸图片
重磅！全球首位AI软件工程师：Devin 来了。。。