Go语言二叉树后序遍历详解（手把手教你实现后序遍历算法）

Go语言实现二叉树结构

首先，我们需要定义一个二叉树节点结构。在Go中，我们可以使用结构体（struct）来表示：

type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}  

这个结构体包含三个字段：节点值 Val，以及指向左子树和右子树的指针 Left 和 Right。

递归实现后序遍历

递归是最直观、最容易理解的实现方式。根据后序遍历的定义，我们先递归处理左子树，再递归处理右子树，最后处理当前节点。

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

这段代码中，我们定义了一个内部函数 dfs（深度优先搜索），它会按照后序的顺序将节点值添加到 result 切片中。

非递归（迭代）实现后序遍历

虽然递归写法简洁，但在某些场景下（如树很深时）可能导致栈溢出。因此，掌握非递归实现也很重要。

后序遍历的非递归实现比前序和中序稍复杂，因为需要确保在访问根节点前，左右子树都已被访问。一种常用技巧是利用两个栈，或者记录上一次访问的节点。

func postorderTraversalIterative(root *TreeNode) []int {    if root == nil {        return []int{}    }        var result []int    stack := []*TreeNode{root}    var lastVisited *TreeNode        for len(stack) > 0 {        current := stack[len(stack)-1]                // 如果当前节点是叶子节点，或者其子节点已被访问        if (current.Left == nil && current.Right == nil) ||           (lastVisited != nil && (lastVisited == current.Left || lastVisited == current.Right)) {            result = append(result, current.Val)            lastVisited = current            stack = stack[:len(stack)-1] // 出栈        } else {            // 先压入右子树，再压入左子树（因为栈是后进先出）            if current.Right != nil {                stack = append(stack, current.Right)            }            if current.Left != nil {                stack = append(stack, current.Left)            }        }    }        return result}  

完整示例与测试

下面是一个完整的可运行示例，包含构建二叉树和两种遍历方式的测试：

package mainimport "fmt"type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}func postorderTraversal(root *TreeNode) []int {    var result []int    var dfs func(*TreeNode)    dfs = func(node *TreeNode) {        if node == nil {            return        }        dfs(node.Left)        dfs(node.Right)        result = append(result, node.Val)    }    dfs(root)    return result}func main() {    // 构建如下二叉树：    //       1    //      / \    //     2   3    //    / \    //   4   5    root := &TreeNode{Val: 1}    root.Left = &TreeNode{Val: 2}    root.Right = &TreeNode{Val: 3}    root.Left.Left = &TreeNode{Val: 4}    root.Left.Right = &TreeNode{Val: 5}    fmt.Println("后序遍历结果:", postorderTraversal(root))    // 输出: [4 5 2 3 1]}  

总结

通过本文，你已经掌握了在Go语言中实现二叉树后序遍历的两种方法：递归和非递归。无论你是准备面试，还是深入学习Go数据结构教程，这些知识都非常实用。

记住后序遍历的核心口诀：“左右根”。多加练习，你就能熟练运用这一基础但强大的算法。

希望这篇关于Go语言二叉树后序遍历的教程对你有帮助！如果你有任何问题，欢迎在评论区留言交流。