数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Go语言程序查找树的直径
在这篇 Go 语言文章中，我们将使用递归和迭代方法来查找树的直径。树的直径是指树中任意两个叶子节点之间最长路径上的节点数。
语法
func diameter(root *node) int{…}
diameter() 函数用于查找树的直径。它以指向根节点的指针作为参数。
算法
**步骤 1** − 首先，我们需要导入 fmt 包。
**步骤 2** − 现在，创建一个名为 node 的树的单个节点的结构体。它包含三个字段，一个是保存节点的整数数据值，第二个和第三个指向左节点和右节点。
**步骤 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)
}
输出
The diameter of the tree is: 2
结论
我们已经成功地编译并执行了一个 Go 语言程序，我们将使用递归和迭代方法来查找树的直径，并附带两个示例。在第一个示例中，我们使用了递归方法；在第二个示例中，我们使用了迭代方法。
225 次查看
