Golang程序：寻找树的直径

在这篇Golang文章中，我们将使用递归和迭代方法来寻找树的直径。树的直径是树中任意两个叶节点之间最长路径上的节点数。

语法

func diameter(root *node) int{…}

diameter()函数用于寻找树的直径。它以指向根节点的指针作为其参数。

算法

• 步骤1− 首先需要导入fmt包。
• 步骤2− 现在，创建一个名为 node 的树的单个节点的结构体。它包含三个字段，一个用于保存节点的整数数据值，另一个和第三个指向左右节点。
• 步骤3− 定义函数 new() 以初始化一个新节点。
• 步骤4− 现在，创建一个名为 diameter() 的函数，该函数以根节点为输入并返回该节点所在的树的直径。
• 步骤5− 树的直径是树中任意两个叶节点之间最长路径上的节点数。
• 步骤6− 如果根节点为 nil ，则返回0。
• 步骤7− 否则，使用height函数计算左右子树的高度，递归使用diameter函数计算左右子树的直径。
• 步骤8− 当前节点所在的树的直径是左右子树高度之和加1和左右子树的直径之间的最大值。
• 步骤9− 现在，创建一个名为 height() 的函数，该函数以根节点作为输入并返回该节点所在的树的高度。
• 步骤10− 如果根节点为nil，则返回0。否则，递归计算左右子树的高度并返回两个高度中的最大值加1。
• 步骤11− 定义 max() 函数以返回两个整数的最大值。
• 步骤12− 开始 main() 函数。在 main() 函数内部，调用新的()函数以向二叉树添加节点。
• 步骤13− 现在，调用 diameter() 函数以寻找树的直径。
• 步骤14− 使用 fmt.Println() 函数将树的直径输出到屏幕上。

例1

在这个例子中，我们将使用递归方法定义一个名为 diameter() 的函数，该函数用于寻找树的直径。

package main

import "fmt"

type node struct {
   left  *node
   right *node
   data  int
}

func new(data int) *node {
   return &node{nil, nil, data}
}

func diameter(root *node) int {
   if root == nil {
      return 0
   }
   leftH := height(root.left)
   rightH := height(root.right)

   leftD := diameter(root.left)
   rightD := diameter(root.right)

   return max(leftH+rightH+1, max(leftD, rightD))
}

func height(root *node) int {
   if root == nil {
      return 0
   }
   return 1 + max(height(root.left), height(root.right))
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

func main() {
   root := new(4)
   root.left = new(3)
   root.right = new(2)
   root.left.left = new(1)
   root.left.right = new(5)

   fmt.Println("Diameter of the tree is: ", diameter(root))
}

输出

Diameter of the tree is:  4

例2

在此示例中，我们将使用迭代方法定义一个 diameter() 函数，该函数用于找到树的直径。

package main

import (
   "fmt"
)

type TreeNode struct {
   val   int
   left, right *TreeNode
}

func diameter(root *TreeNode) int {
   if root == nil {
      return 0
   }

   stack := []*TreeNode{root}

   visited := make(map[*TreeNode]bool)

   maxDiameters := make(map[*TreeNode]int)

   maxDiameter := 0

   for len(stack) > 0 {
      node := stack[len(stack)-1]
      stack = stack[:len(stack)-1]

      visited[node] = true

      leftDiameter := 0
      rightDiameter := 0

      if node.left != nil {
         if _, ok := visited[node.left]; !ok {
            stack = append(stack, node.left)
         }
         leftDiameter = maxDiameters[node.left] + 1
      }

      if node.right != nil {
         if _, ok := visited[node.right]; !ok {
            stack = append(stack, node.right)
         }
         rightDiameter = maxDiameters[node.right] + 1
      }

      maxDiameter = max(maxDiameter, leftDiameter+rightDiameter)

      maxDiameters[node] = max(leftDiameter, rightDiameter)
   }

   return maxDiameter
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

func main() {

   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}
   root.left.left.left = &TreeNode{val: 6}
   root.left.left.right = &TreeNode{val: 7}
   root.left.left.right.left = &TreeNode{val: 8}
   root.left.left.right.left.right = &TreeNode{val: 9}

   diameter := diameter(root)

   fmt.Printf("树的直径为： %d.\n", diameter)
}

输出

树的直径为： 2

结论

我们已经成功编译和执行了一个Go语言程序，通过使用递归和迭代方法一起来找到树的直径，同时提供了两个例子。第一个例子中，我们使用了递归方法，在第二个例子中，我们使用了迭代方法。