Golang程序：在二叉搜索树中查找节点深度

什么是二叉搜索树？

在讲如何查找节点深度之前，我们需要先了解什么是二叉搜索树。二叉搜索树是一种非常常见的二叉树，它的每个节点上都存储着一个值，且该节点的左子树中的每个节点都小于它，右子树中的每个节点都大于它。这个特点使得我们可以非常快速地在二叉搜索树中查找某个值。

下面是一个二叉搜索树的例子：

实现代码

我们首先要定义一个二叉树的节点，它包含一个值和左右子节点的指针。下面是节点的定义：

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

接下来我们需要写一个函数来插入新的节点。由于这是一个二叉搜索树，所以插入新节点时，我们需要保证它符合二叉搜索树的性质。下面是插入节点的代码：

func insert(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }

    if val < root.Val {
        root.Left = insert(root.Left, val)
    } else if val > root.Val {
        root.Right = insert(root.Right, val)
    }

    return root
}

现在我们已经有了一个二叉搜索树并能插入新的节点，下一步就是写一个函数来查找某个节点的深度。节点深度的定义为从根节点到该节点所经过的边的个数。下面是查找深度的代码：

func depth(root *TreeNode, val int) int {
    if root == nil {
        return 0
    }

    if root.Val == val {
        return 1
    } else if root.Val > val {
        return depth(root.Left, val) + 1
    } else {
        return depth(root.Right, val) + 1
    }
}

我们可以通过递归来查找节点深度。如果节点等于根节点，直接返回深度1；如果节点小于根节点，就继续递归左子树；如果节点大于根节点，就继续递归右子树。

为了方便测试，下面是用于构建二叉搜索树和查找节点深度的完整代码：

func main() {
    node := &TreeNode{Val: 4}
    insert(node, 2)
    insert(node, 1)
    insert(node, 3)
    insert(node, 6)
    insert(node, 5)
    insert(node, 7)

    fmt.Println(depth(node, 7)) // 输出3
}