理想汽车面试太变态了，脑袋嗡嗡的！
P
C语言专栏约 3 分钟
C语言专栏约 3 分钟同学信心满满地说后序遍历是“左-中-右”，结果面试官一本正经地反驳说不是。这下好了，把那同学给整懵逼了。 来，给大家普及下知识点，二叉树的后序遍历其实就是“左-右-中”。但这面试官，不知是故意的还是怎样，这么一整，直接让人摸不着头脑。 网友也是各种评论调侃整花活，哈哈。 所以啊，面试有时候不仅仅是考察你的技术能力，更是一场心理游戏。 正好今天提到了二叉树的后序遍历，而且这个算法确实是很重要，那么今天的算法题我们就来看一看这二叉树的后序遍历。
下面分享一道大厂的算法题
今日算法题，来自LeetCode的第145题：二叉树的后序遍历，下面是我的算法思路及实现，让我们来看看吧。
算法题目
给定一个二叉树，返回它的后序遍历结果。
算法思路
递归法
递归遍历左子树
递归遍历右子树
访问根节点 迭代法
使用栈模拟递归过程：
创建一个栈来存储节点，以及一个用于存储结果的列表。
迭代处理：将根节点入栈，然后迭代执行以下操作，直到栈为空：
弹出栈顶元素，将其值添加到结果列表的前面（这是为了保证访问顺序为左、右、根）。
先将左子节点入栈，然后是右子节点（这样可以保证右子节点先被处理）。
专属福利 👉点击领取：最全Python资料合集
代码实现
#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 nodespostorderTraversalRec(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 = valself.left = leftself.right = rightdef postorderTraversal(root: TreeNode) -> [int]:def recur(node):if not node:returnrecur(node.left)recur(node.right)result.append(node.val)result = []recur(root)return result
算法解析
后序遍历的实现主要有两种方式：递归和迭代。递归实现比较直观，但迭代实现可以提供更好的空间效率。无论哪种方式，核心思想都是遵循左子树、右子树、根节点的访问顺序。
示例和测试
1\2/3
后序遍历的结果应该是 [3,2,1]。
总结
二叉树的后序遍历是基础且重要的算法，掌握其递归和迭代两种实现方式对深入理解树结构和相关算法非常有帮助。
热门推荐