LeetCode 145. 二叉树的后序遍历

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 145. 二叉树的后序遍历

思路分析

后序遍历的顺序为：左子树 → 右子树 → 根节点。

参考代码

// 前序遍历
func preorderTraversal(root *TreeNode) []int {
	var res []int

	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		res = append(res, node.Val) // 根
		dfs(node.Left)              // 左
		dfs(node.Right)             // 右
	}

	dfs(root)
	return res
}

// 中序遍历
func inorderTraversal(root *TreeNode) []int {
	var res []int

	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		dfs(node.Left)              // 左
		res = append(res, node.Val) // 根
		dfs(node.Right)             // 右
	}

	dfs(root)
	return res
}

// 后序遍历
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
}

// 后序遍历
func postorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	var res []int
	var stack []*TreeNode
	stack = append(stack, 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
}

func postorderTraversal(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}

	var stack []*TreeNode
	var res []int
	stack = append(stack, root)

	for len(stack) > 0 {
		cur := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append([]int{cur.Val}, res...) // 逆序插入

		if cur.Left != nil {
			stack = append(stack, cur.Left)
		}
		if cur.Right != nil {
			stack = append(stack, cur.Right)
		}
	}

	return res
}

时间复杂度：O (n)，其中 n 是二叉树的节点数。

空间复杂度：O (h)，其中 h 是二叉树的高度。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

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