Golang 查找树的直径

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

语法

func diameter(root *node) int{…}

diameter()函数用于查找树的直径。它将根节点的指针作为参数。

步骤

步骤 1 - 首先，我们需要导入fmt包。
步骤 2 - 现在，创建一个名为node的树的单个节点的struct。它包含三个字段，一个用于保存节点的整数数据值，另外两个指向左节点和右节点。
步骤 3 - 定义一个名为new()的函数来初始化一个新的节点。
步骤 4 - 现在，创建一个名为diameter()的函数，它接受一个根节点作为输入，并返回以该节点为根的树的直径。
步骤 5 - 树的直径是树中任意两个叶子节点之间最长路径上的节点数。
步骤 6 - 如果根节点为nil，则返回0。
步骤 7 - 否则，使用height函数计算左子树和右子树的高度，并使用diameter函数递归地计算左子树和右子树的直径。
步骤 8 - 当前节点为根的树的直径是左子树和右子树高度之和加一，以及左子树和右子树的直径中的最大值。
步骤 9 - 现在，创建一个名为height()的函数，它接受一个根节点作为输入，并返回以该节点为根的树的高度。
步骤 10 - 如果根节点为nil，则返回0。否则，递归地计算左子树和右子树的高度，并返回两个高度中的最大值加一。
步骤 11 - 定义max()函数来返回两个整数中的最大值。
步骤 12 - 开始main()函数。在main()函数内部，调用new()函数向二叉树添加节点。
步骤 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("The diameter of the tree is: %d.\n", diameter)
}