树与图简单2 种解法

#145二叉树的后序遍历

按左子树、右子树、根节点的顺序返回节点值。

#二叉树#深度优先搜索#栈

解题主线

迭代可生成“根—右—左”，再通过头插得到“左—右—根”。

解法 1：递归后序遍历

先递归左右子树，最后记录根节点。

时间复杂度

O(n)

空间复杂度

O(h)

145. 二叉树的后序遍历 · 递归后序遍历

java

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)

145. 二叉树的后序遍历 · 栈与双端结果

java

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