LeetCode 145: Binary Tree Postorder Traversal (Tree Traversal)
LeetCode 145Binary TreeStackToday we solve LeetCode 145 - Binary Tree Postorder Traversal.
Source: https://leetcode.com/problems/binary-tree-postorder-traversal/
English
Problem Summary
Given the root of a binary tree, return its node values in postorder: left -> right -> root. Example: for tree [1,null,2,3], answer is [3,2,1].
Key Insight
Recursive postorder is straightforward, but iterative postorder is the interview focus. With one stack plus a prev pointer (last visited node), we can know whether a node's right subtree is already done. Only then do we output the current node.
Brute Force and Limitations
The baseline is recursion (DFS): traverse left subtree, then right subtree, then append root. It is elegant but depends on call stack depth. For very skewed trees, recursion depth can be large, so iterative control is safer in constrained environments.
Optimal Algorithm Steps (Iterative, One Stack)
1) Move down left children and push nodes into stack.
2) Peek stack top as node.
3) If node.right is null or already visited (node.right == prev), output node, pop, set prev = node.
4) Otherwise move to node.right and continue.
5) Repeat until stack and current pointer are both empty.
Complexity Analysis
Time: O(n), each node is pushed/popped once.
Space: O(h) average (h is tree height), worst-case O(n) for skewed tree.
Common Pitfalls
- Forgetting the prev check causes repeated right-subtree traversal.
- Using root-right-left and forgetting final reverse when using the two-phase variant.
- Not handling null root.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
TreeNode prev = null;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.peek();
if (node.right == null || node.right == prev) {
ans.add(node.val);
stack.pop();
prev = node;
} else {
cur = node.right;
}
}
return ans;
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) []int {
ans := make([]int, 0)
stack := make([]*TreeNode, 0)
cur := root
var prev *TreeNode = nil
for cur != nil || len(stack) > 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
node := stack[len(stack)-1]
if node.Right == nil || node.Right == prev {
ans = append(ans, node.Val)
stack = stack[:len(stack)-1]
prev = node
} else {
cur = node.Right
}
}
return ans
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* prev = nullptr;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) {
st.push(cur);
cur = cur->left;
}
TreeNode* node = st.top();
if (node->right == nullptr || node->right == prev) {
ans.push_back(node->val);
st.pop();
prev = node;
} else {
cur = node->right;
}
}
return ans;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
stack = []
cur = root
prev = None
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
node = stack[-1]
if node.right is None or node.right is prev:
ans.append(node.val)
stack.pop()
prev = node
else:
cur = node.right
return ans/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var postorderTraversal = function(root) {
const ans = [];
const stack = [];
let cur = root;
let prev = null;
while (cur !== null || stack.length > 0) {
while (cur !== null) {
stack.push(cur);
cur = cur.left;
}
const node = stack[stack.length - 1];
if (node.right === null || node.right === prev) {
ans.push(node.val);
stack.pop();
prev = node;
} else {
cur = node.right;
}
}
return ans;
};中文
题目概述
给定二叉树根节点，返回其后序遍历结果，顺序是 左 -> 右 -> 根。例如树 [1,null,2,3] 的输出是 [3,2,1]。
核心思路
递归法最直观，但面试常追问迭代。这里用「单栈 + prev 指针」：prev 记录上一次完成访问的节点。只有当当前节点右子树为空或右子树已经访问完，才能把当前节点加入答案。
暴力解法与不足
基线做法是递归 DFS（左、右、根），写起来短且不易错；但它依赖系统调用栈。极端退化树会让递归深度很高，所以工程上常偏向显式栈迭代。
最优算法步骤（迭代单栈）
1）一路向左，把路径节点入栈。
2）查看栈顶节点 node。
3）若 node.right 为空，或 node.right == prev，说明右子树已处理：输出并弹栈，更新 prev。
4）否则转向其右子树继续。
5）直到当前指针为空且栈为空结束。
复杂度分析
时间复杂度：O(n)，每个节点最多入栈出栈一次。
空间复杂度：平均 O(h)，最坏（链状树）为 O(n)。
常见陷阱
- 忘记 prev 判断，导致右子树反复进入。
- 混用“根右左后反转”写法时漏掉反转步骤。
- 未处理空树输入。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
TreeNode prev = null;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.peek();
if (node.right == null || node.right == prev) {
ans.add(node.val);
stack.pop();
prev = node;
} else {
cur = node.right;
}
}
return ans;
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) []int {
ans := make([]int, 0)
stack := make([]*TreeNode, 0)
cur := root
var prev *TreeNode = nil
for cur != nil || len(stack) > 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
node := stack[len(stack)-1]
if node.Right == nil || node.Right == prev {
ans = append(ans, node.Val)
stack = stack[:len(stack)-1]
prev = node
} else {
cur = node.Right
}
}
return ans
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* prev = nullptr;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) {
st.push(cur);
cur = cur->left;
}
TreeNode* node = st.top();
if (node->right == nullptr || node->right == prev) {
ans.push_back(node->val);
st.pop();
prev = node;
} else {
cur = node->right;
}
}
return ans;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
stack = []
cur = root
prev = None
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
node = stack[-1]
if node.right is None or node.right is prev:
ans.append(node.val)
stack.pop()
prev = node
else:
cur = node.right
return ans/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var postorderTraversal = function(root) {
const ans = [];
const stack = [];
let cur = root;
let prev = null;
while (cur !== null || stack.length > 0) {
while (cur !== null) {
stack.push(cur);
cur = cur.left;
}
const node = stack[stack.length - 1];
if (node.right === null || node.right === prev) {
ans.push(node.val);
stack.pop();
prev = node;
} else {
cur = node.right;
}
}
return ans;
};
Comments