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