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

开启您的职业生涯

完成课程获得认证

开始学习
广告