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)
}