Golang 执行后序遍历

在Go中，后序遍历是一种技术，先访问左子节点，然后访问右子节点，最后访问根节点。这种顺序经常用于对树执行某些操作，包括释放树所消耗的内存。我们将使用两种方法实现后序遍历，第一种方法使用切片，第二种方法使用栈。

语法

func append(slice, element_1, element_2…, element_N) []T

append函数用于将值添加到数组切片中。它接受多个参数。第一个参数是要添加值的数组，其后是要添加的值。函数然后返回包含所有值的最终数组切片。

方法1：使用切片

在这种方法中，首先检查根节点是否为空。如果是，则返回一个空切片。如果不是，则继续探索左子树和右子树，并将结果添加到我们的结果切片中。然后，在结果中添加当前节点的值后，返回结果切片。

步骤

• 步骤1 - 在程序中创建一个主包，并声明fmt（格式包）和strings包，其中main产生可执行代码，fmt帮助格式化输入和输出。

• 步骤2 - 创建一个TreeNode结构以表示二叉树的节点。

• 步骤3 - 创建一个名为post_order_traversal的函数，以便按后序遍历树。

• 步骤4 - 验证根节点是否为空。如果是，则返回一个空切片。

• 步骤5 - 在左子节点上调用post_order_traversal来迭代地探索左子树。

• 步骤6 - 在右子节点上调用post_order_traversal以迭代地遍历右子树。

• 步骤7 - 将当前节点的值添加到结果切片中。

• 步骤8 - 返回结果切片。

• 步骤9 - 后序遍历函数递归地遍历整个树，并将结果记录在一个切片中。函数按照后序遍历的顺序将节点的值添加到结果切片中。

示例

在这个示例中，我们将使用切片来存储左子树和右子树探索后的结果。

package main
import "fmt"

// Definition for a binary tree node.
type TreeNode struct {
   Val  int
   Left_val  *TreeNode
   Right_val *TreeNode
}

func post_order_traversal(root *TreeNode) []int {
   var result []int
   if root == nil {
      return result
   }
   result = append(result, post_order_traversal(root.Left_val)...)
   result = append(result, post_order_traversal(root.Right_val)...)
   result = append(result, root.Val)
   return result
}

func main() {
   root := &TreeNode{Val: 10}     //assign values to the list
   root.Left_val = &TreeNode{Val: 20}
   root.Right_val = &TreeNode{Val: 30}
   root.Left_val.Left_val = &TreeNode{Val: 40}
   root.Left_val.Right_val = &TreeNode{Val: 50}
   result := post_order_traversal(root)
   fmt.Println("The postorder traversal is created here:")
   fmt.Println(result) //print the postorder traversal
}

输出

The postorder traversal is created here:
[40 50 20 30 10]

方法2：使用栈实现后序遍历

在这种方法中，我们使用栈来跟踪后序遍历中要访问的节点。首先将根节点推入栈中。在每次迭代之后，从栈中移除顶部节点，将其值添加到结果数组中，然后将顶部节点的右子节点和左子节点重新推入栈中。通过以这种方式以相反顺序访问节点，我们可以通过将值附加到结果数组的前面来构建正确的后序排序的结果数组。

步骤

• 步骤 1 − 在程序中创建一个名为main的包并声明fmt(format包)和strings包，其中main用于生成可执行代码，fmt用于格式化输入和输出。

• 步骤 2 − 创建一个TreeNode结构来表示二叉树的节点。

• 步骤 3 − 创建名为post_order_traversal的函数，以按后序遍历树。

• 步骤 4 − 验证根节点是否为空。如果为空，则返回一个空数组。

• 步骤 5 − 从头开始创建一个栈，并将根节点添加到栈中。

• 步骤 6 − 重复以下步骤，直到栈为空。

a. 移除栈的顶部节点。

b. 将节点的值作为前缀添加到结果数组中。

c. 将左子节点和右子节点添加到栈中。

• 步骤 7 − 返回结果数组。

• 步骤 8 − 使用fmt.Println()函数将结果打印到控制台，其中ln表示换行。

示例

在这个示例中，我们将使用栈来实现后序遍历。

package main
import "fmt"

// Definition for a binary tree node.
type TreeNode struct {
   Val   int
   Left_val  *TreeNode
   Right_val *TreeNode
}

func post_order_traversal(root *TreeNode) []int {
   var result []int
   if root == nil {
      return result
   }
   stack := []*TreeNode{root}
   for len(stack) > 0 {
      node := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      result = append([]int{node.Val}, result...)
      if node.Left_val != nil {
         stack = append(stack, node.Left_val)
      }
      if node.Right_val != nil {
         stack = append(stack, node.Right_val)
      }
   }
   return result
}

func main() {
   root := &TreeNode{Val: 10}   //assign the values to the list
   root.Left_val = &TreeNode{Val: 20}
   root.Right_val = &TreeNode{Val: 30}
   root.Left_val.Left_val = &TreeNode{Val: 40}
   root.Left_val.Right_val = &TreeNode{Val: 50}
   result := post_order_traversal(root)
   fmt.Println("The postorder traversal created here is:")
   fmt.Println(result)
}

输出

The postorder traversal created here is:
[40 50 20 30 10]

结论

我们使用两个示例执行了后序树遍历程序。在第一个示例中，我们使用结果切片在左子树和右子树被探索后存储结果；而在第二个示例中，我们使用栈来执行这个操作。