資料結構
網路
關係資料庫管理系統 (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
廣告