Golang 二叉树的左视图

在编程中，二叉树的编码问题经常在面试中被问到，问题的描述是找到二叉树的左视图。如果我们试图更多地理解问题陈述，那么我们可以这样解释：当站在树的左侧时，所有的节点都是可见的。

示例说明

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

第1层: 迭代节点1，没有左侧节点，进入下一层。节点1在左视图中可见。

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

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

范例

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

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分别是图中顶点和边的数量。要了解更多关于Golang的信息，你可以探索这些教程。