理想汽車面試太變態了，腦袋嗡嗡的！

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