LeetCode 145. 二叉树的后序遍历

Categories:

Tags:

题目描述
思路分析
1. 解法一：迭代（前序变种+反转，推荐）
2. 解法二：递归
相似题目

题目描述

✅ 145. 二叉树的后序遍历

思路分析

解法一：迭代（前序变种+反转，推荐）

核心思路：

后序遍历顺序为左→右→根，直接用栈模拟较为复杂

观察前序遍历（根→左→右），将其改为根→右→左，再对结果整体翻转，即得左→右→根的后序序列

入栈时先压左子节点、再压右子节点，弹栈后将节点值追加到结果，最终反转结果数组

复杂度分析：

时间复杂度：O(n)，其中 n 为二叉树的节点数，每个节点恰好访问一次

空间复杂度：O(n)，栈的最大深度为 n（退化为链表时）

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            // 将节点值插入结果头部，实现逆序（等价于最后翻转）
            res.add(0, node.val);
            // 先压左子节点，再压右子节点，弹出顺序为根→右→左，头插后得到左→右→根
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        return res;
    }
}

func postorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var res []int
	stack := []*TreeNode{root}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, node.Val)
		// 先压左子节点，再压右子节点，弹出顺序为根→右→左
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	// 翻转结果数组，得到左→右→根的后序序列
	for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
		res[i], res[j] = res[j], res[i]
	}
	return res
}

解法二：递归

核心思路：

递归是后序遍历最直观的实现，天然遵循左→右→根的顺序

先递归遍历左子树，再递归遍历右子树，最后将当前节点值加入结果

复杂度分析：

时间复杂度：O(n)，其中 n 为二叉树的节点数，每个节点恰好访问一次

空间复杂度：O(h)，其中 h 为树的高度，递归调用栈深度最坏为 n（退化为链表时）

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    private void dfs(TreeNode node, List<Integer> res) {
        if (node == null) {
            return;
        }
        // 先遍历左子树
        dfs(node.left, res);
        // 再遍历右子树
        dfs(node.right, res);
        // 最后处理根节点
        res.add(node.val);
    }
}

func postorderTraversal(root *TreeNode) []int {
	var res []int
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		// 先遍历左子树
		dfs(node.Left)
		// 再遍历右子树
		dfs(node.Right)
		// 最后处理根节点
		res = append(res, node.Val)
	}
	dfs(root)
	return res
}

相似题目

题目	难度	考察点
94. 二叉树的中序遍历	简单	递归 / 迭代 / 中序遍历
144. 二叉树的前序遍历	简单	递归 / 迭代 / 前序遍历
102. 二叉树的层序遍历	中等	BFS / 队列
589. N 叉树的前序遍历	简单	递归 / 迭代 / DFS
590. N 叉树的后序遍历	简单	递归 / 迭代 / DFS
341. 扁平化嵌套列表迭代器	中等	迭代器 / 栈 / DFS
987. 二叉树的垂序遍历	困难	DFS + 排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/87975351