LeetCode 145. 二叉树的后序遍历

Categories:

Tags:

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

题目描述

🔥 145. 二叉树的后序遍历

思路分析

后序遍历的基本思路是递归地访问左子树，然后访问右子树，最后访问根节点。可以使用栈来实现非递归的后序遍历。具体步骤如下：

创建一个栈，用于存储节点。

创建一个结果数组 res，用于存储遍历结果。

将根节点压入栈中。

当栈不为空时，弹出栈顶节点，将其值添加到 res 中。

如果弹出的节点有左子节点，将左子节点压入栈中；如果有右子节点，将右子节点压入栈中。

最后，反转 res 数组，得到后序遍历的结果。

参考代码

// 前序遍历函数
func preorderTraversal(root *TreeNode) []int {
	var res []int
	var helper func(node *TreeNode)
	helper = func(node *TreeNode) {
		if node == nil {
			return
		}
		res = append(res, node.Val) // 访问根节点
		helper(node.Left)           // 递归访问左子树
		helper(node.Right)          // 递归访问右子树
	}
	helper(root)
	return res
}

// 中序遍历函数
func inorderTraversal(root *TreeNode) []int {
	var res []int
	var helper func(node *TreeNode)
	helper = func(node *TreeNode) {
		if node == nil {
			return
		}
		helper(node.Left)           // 递归访问左子树
		res = append(res, node.Val) // 访问根节点
		helper(node.Right)          // 递归访问右子树
	}
	helper(root)
	return res
}

// 后序遍历函数
func postorderTraversal(root *TreeNode) []int {
	var res []int
	var helper func(node *TreeNode)
	helper = func(node *TreeNode) {
		if node == nil {
			return
		}
		helper(node.Left)           // 递归访问左子树
		helper(node.Right)          // 递归访问右子树
		res = append(res, node.Val) // 访问根节点
	}
	helper(root)
	return res
}

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

空间复杂度：O (n)，最坏情况下，递归栈的深度为 n。

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

	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
}

时间复杂度：O (n)，其中 n 是二叉树的节点数。每个节点都被访问一次。

空间复杂度：O (h)，其中 h 是二叉树的高度。最坏情况下，栈的空间复杂度为 O (n)，在树呈现链状时。

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

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