理想汽车面试太变态了，脑袋嗡嗡的！

2024-03-17码农

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

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

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

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

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

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

下面是今日算法题

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

# 算法题目

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

# 算法思路

递归法

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

迭代法

使用栈模拟递归过程：

创建一个栈来存储节点，以及一个用于存储结果的列表。
迭代处理：将根节点入栈，然后迭代执行以下操作，直到栈为空：

弹出栈顶元素，将其值添加到结果列表的前面（这是为了保证访问顺序为左、右、根）。

先将左子节点入栈，然后是右子节点（这样可以保证右子节点先被处理）。

# 代码实现

C语言实现(递归)

#include<stdio.h>#include<stdlib.h>typedefstructTreeNode {int val;structTreeNode *left;structTreeNode *right;} TreeNode;voidpostorderTraversalRec(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 classTreeNode {int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }} classSolution {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实现(递归)

classTreeNode:def__init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdefpostorderTraversal(root: TreeNode) -> [int]:defrecur(node):ifnotnode:return recur(node.left) recur(node.right) result.append(node.val) result = [] recur(root)return result