【力扣】145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点的数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

题解：

递归法：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
func postorderTraversal(root *TreeNode) []int {
	var result []int
	var postorder func(node *TreeNode)
	postorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		postorder(node.Left)
		postorder(node.Right)
		result = append(result, node.Val)
	}
	postorder(root)
	return result
}

迭代法+双指针法：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
func postorderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}
	st := list.New()
	st.PushBack(root)
	for st.Len() > 0 {
		// 返回尾部最后一个节点并删除掉
		node := st.Remove(st.Back()).(*TreeNode)
		result = append(result, node.Val)
		// 基于栈先进后出的原则，这里入栈的时候先让左节点进入再让右节点进
		// 出栈的时候优先从右节点出，再从左节点出。目前顺序是：中 右 左
		if node.Left != nil {
			st.PushBack(node.Left)
		}
		if node.Right != nil {
			st.PushBack(node.Right)
		}
	}
	// 定义一个名为 reverse 的闭包函数，可以通过双指针反转结果
	reverse := func(data []int) {
		left, right := 0, len(data)-1
		for left < right {
			data[left], data[right] = data[right], data[left]
			left++
			right--
		}
	}
	reverse(result)
	return result
}

第二种迭代法：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
func postorderTraversal(root *TreeNode) []int {
	var result []int
	// 创建一个栈 并将 root 节点压入栈
	stack := list.New()
	stack.PushBack(root)
	// 遍历二叉树各个节点
	for stack.Len() > 0 {
		// 取出并删除二叉树栈顶元素
		e := stack.Back()
		stack.Remove(e)
		// 栈顶元素如果为 nil，说明需要遍历当前节点
		if e.Value == nil {
			// 取出并删除下一个栈顶元素（当前节点）
			e = stack.Back()
			stack.Remove(e)
			node := e.Value.(*TreeNode)
			result = append(result, node.Val)
			continue
		}
		node := e.Value.(*TreeNode)
		// 压入当前节点后再压入一个 nil 做标记
		stack.PushBack(node)
		stack.PushBack(nil)
		// 如果右子树非空，将右子节点压入栈
		if node.Right != nil {
			stack.PushBack(node.Right)
		}
		// 如果左子树非空，将左子节点压入栈
		if node.Left != nil {
			stack.PushBack(node.Left)
		}
	}
	return result
}