数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究Go语言程序：二叉树的右视图
在编程中，二叉树的编码问题在面试中经常被问到，问题陈述是找到二叉树的右视图。如果我们尝试理解问题陈述中右视图的具体含义，我们可以这样解释：站在树的右侧时可以看到的所有节点。
图解
让我们通过一个例子来更好地理解。假设我们有如下所示的树，如果我们站在右侧，可见的节点将是1、4和7。节点3和2被节点4隐藏，节点5和6被节点7隐藏。为了实现这一点，我们将使用广度优先搜索算法进行层序遍历。对于每一层，我们将从右侧开始迭代，并在每一层结束时更新一个变量，该变量的值将是最右边的值。
第1层：迭代节点1，左侧没有节点，移动到下一层。节点1在这一层右视图中可见。
第2层：开始迭代节点2并更新变量的值。移动到节点3并更新变量的值，然后移动到节点4。节点4在这一层右视图中可见。
第3层：从节点5开始并更新变量的值。移动到节点6并更新变量的值，然后移动到节点7。节点7在这一层右视图中可见。
示例
在这个代码中，我们实现了队列数据结构及其函数，目前Go语言中没有预构建的队列库。
package main
import "fmt"
type Queue struct {
List [](*TreeNode)
}
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// function to add element in queue
func (q *Queue) Enqueue(element *TreeNode) {
q.List = append(q.List, element)
}
// function to delete element in the queue
func (q *Queue) Dequeue() *TreeNode {
if q.isEmpty() {
fmt.Println("Queue is empty.")
return nil
}
element := q.List[0]
q.List = q.List[1:]
return element
}
// function check that queue is empty or not
func (q *Queue) isEmpty() bool {
return len(q.List) == 0
}
// function to find the length of the queue
func (q *Queue) size() int {
return len(q.List)
}
// creating binary tree
func CreateBinaryTree(root *TreeNode) {
n1 := TreeNode{1, nil, nil}
n2 := TreeNode{2, nil, nil}
root.Left = &n1
root.Right = &n2
n3 := TreeNode{3, nil, nil}
n4 := TreeNode{4, nil, nil}
n1.Left = &n3
n1.Right = &n4
n5 := TreeNode{5, nil, nil}
n6 := TreeNode{6, nil, nil}
n2.Left = &n5
n2.Right = &n6
}
// RightView a function with root node as argument
// and returns the right view elements in the array
func RightView(root *TreeNode) []int {
// returning empty array if tree is empty
if root == nil {
return []int{}
}
// creating vaiable for queue
var q Queue
// creating array to store right side element
var rightView []int
// variable to store right most value at current level
var Val int
// enqueue root address in the queue
q.Enqueue(root)
q.Enqueue(nil)
// breadth first search over tree
for q.size() > 1 {
currNode := q.Dequeue()
if currNode == nil {
q.Enqueue(nil)
rightView = append(rightView, Val)
continue
}
Val = currNode.Val
if currNode.Left != nil {
q.Enqueue(currNode.Left)
}
if currNode.Right != nil {
q.Enqueue(currNode.Right)
}
}
rightView = append(rightView, Val)
return rightView
}
func main() {
fmt.Println("Golang program to find right view of binary tree.")
// creating root node of binary tree
root := TreeNode{0, nil, nil}
// calling CreateBinaryTree function to create complete binary tree
CreateBinaryTree(&root)
// calling RightView function
rightView := RightView(&root)
// print right view element
for i := 0; i < len(rightView); i++ {
fmt.Print(rightView[i], " ")
}
fmt.Println()
}
输出
Golang program to find right view of binary tree. 0 2 6
结论
通过这种方式，我们使用广度优先搜索算法进行层序遍历，找到了二叉树的右视图。我们也可以使用深度优先搜索算法来查找树的层序遍历。这种方法的时间复杂度为O(V + E)，其中V和E分别是图中顶点数和边数。要了解更多关于Go语言的信息，您可以浏览这些教程。
更新于：2023年7月10日
浏览量：103
广告