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

开启你的职业生涯

完成课程获得认证

开始学习
广告