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