树与图简单2 种解法
#145二叉树的后序遍历
按左子树、右子树、根节点的顺序返回节点值。
#二叉树#深度优先搜索#栈
原题
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
解题主线
- 迭代可生成“根—右—左”，再通过头插得到“左—右—根”。
解法 1：递归后序遍历
先递归左右子树，最后记录根节点。
-
时间复杂度： O(n)
-
空间复杂度： O(h)
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// 最终结果必须保持“左子树、右子树、根节点”的后序次序。
// 空节点不产生结果，每个非空节点只会递归访问或入栈一次。
List<Integer> result = new ArrayList<>();
postorder(root, result);
return result;
}
private void postorder(TreeNode node, List<Integer> result) {
if (node == null) return;
postorder(node.left, result);
postorder(node.right, result);
result.add(node.val);
}
}解法 2：栈与双端结果
栈按左后右压入，弹出形成根—右—左；每个值头插形成后序。
-
时间复杂度： O(n)
-
空间复杂度： O(n)
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// 最终结果必须保持“左子树、右子树、根节点”的后序次序。
// 空节点不产生结果，每个非空节点只会递归访问或入栈一次。
if (root == null) return new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
Deque<Integer> result = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.addFirst(node.val);
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
return new ArrayList<>(result);
}
}边界与易错点
- 循环中必须使用刚弹出的 node 访问孩子，不能误用初始 root。
- ArrayList 头插是 O(n)，应使用双端队列。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q145_tree_postorder.javaleetcode/src/main/java/tree/Q94_144_145_traversal.java