Golang 二叉树的右视图

在编程中，关于二叉树有一个常见的编码问题，在面试中经常被问到，问题描述是找到二叉树的右视图。如果我们试图理解问题陈述比仅仅认识右视图更多，那么我们可以解释为当你站在二叉树的右侧时，你可以看到所有的节点。

示例

让我们通过一个示例更好地理解。假设我们有下面的二叉树，如果我们站在右侧，可见的节点将是1、4和7。节点3和2被节点4隐藏，节点5和节点6被节点7隐藏。为了实现这一点，我们将使用广度优先搜索算法进行层次遍历。对于每一层，我们将从右侧开始，并在每一层结束时更新一个变量的值，该变量的值将是左侧的最左值。

Level 1: 遍历节点1，没有左侧的节点，移动到下一层。节点1在右视图中可见。

Level 2: 开始遍历节点2并更新变量的值。移动到节点3并更新变量的值，然后移动到节点4。节点4在左视图中可见。

Level 3: 从节点5开始并更新变量的值。移动到节点6并更新变量的值，然后移动到节点7。节点7在左视图中可见。

示例

在这段代码中，我们实现了一个队列数据结构及其函数，并且目前在Golang中没有预先构建的队列库。

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分别表示图中的顶点数和边数。要了解更多关于Golang的信息，请探索以下教程。