Go语言二叉树高度计算详解（从零开始掌握递归求树高）

Go语言实现二叉树节点结构

首先，我们需要定义一个二叉树的节点结构。在 Go 中，我们通常使用 struct 来表示：

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

每个节点包含一个整数值 Val，以及指向左子树和右子树的指针。

递归法计算二叉树高度

计算二叉树高度最经典的方法是使用递归。其核心思想是：

树的高度 = 1 + max(左子树高度, 右子树高度)

如果当前节点为空，则高度为 -1（因为我们按边数计算）。

完整代码实现

package mainimport "fmt"type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}// 计算二叉树的高度（按边数计算，空树高度为-1）func treeHeight(root *TreeNode) int {    // 基准情况：如果节点为空，返回 -1    if root == nil {        return -1    }        // 递归计算左右子树的高度    leftHeight := treeHeight(root.Left)    rightHeight := treeHeight(root.Right)        // 返回较大的高度 + 1    if leftHeight > rightHeight {        return leftHeight + 1    }    return rightHeight + 1}// 辅助函数：创建新节点func newNode(val int) *TreeNode {    return &TreeNode{Val: val}}func main() {    // 构建如下二叉树：    //       1    //      / \    //     2   3    //    / \    //   4   5    root := newNode(1)    root.Left = newNode(2)    root.Right = newNode(3)    root.Left.Left = newNode(4)    root.Left.Right = newNode(5)        fmt.Printf("二叉树的高度为: %d\n", treeHeight(root)) // 输出: 2}

代码解析

1. treeHeight 函数接收一个 *TreeNode 类型的参数。

2. 如果传入的节点为 nil（即空树），直接返回 -1。

3. 否则，分别递归调用自身计算左子树和右子树的高度。

4. 取两者中的最大值，加 1 后返回，即为当前树的高度。

时间与空间复杂度

- 时间复杂度：O(n)，其中 n 是树中节点的数量。因为每个节点都会被访问一次。

- 空间复杂度：O(h)，其中 h 是树的高度，由递归调用栈的深度决定。最坏情况下（树退化为链表），空间复杂度为 O(n)。

小结

通过本教程，你已经掌握了在 Go语言 中如何使用递归方法计算二叉树的高度。这是学习更复杂树算法（如平衡二叉树、AVL树等）的重要基础。记住，理解递归的关键在于明确基准条件和递归关系。

无论你是准备面试，还是深入学习 Go数据结构教程，掌握二叉树深度计算都是必不可少的技能。希望这篇关于Go语言二叉树高度的详细讲解能帮助你打下坚实基础！

动手试试吧！修改代码，构建不同的树结构，观察高度变化，加深理解。