golang 中序遍历

在Golang中，树是一种常见的数据结构，用于表示层次关系或分层数据。树由节点组成，每个节点可以有一个或多个子节点。而树的遍历则是按照一定规则遍历树的所有节点，以获取树的各个元素或执行特定操作。中序遍历是一种经典的树遍历算法，本文将介绍如何在Golang中实现中序遍历。

什么是中序遍历

中序遍历是一种二叉树的遍历方式，它遍历的顺序为“左根右”。对于给定的二叉树，中序遍历首先遍历其左子树，再访问根节点，最后遍历其右子树。中序遍历是一种重要的二叉树遍历方式，它可以用于从小到大输出二叉搜索树中的所有节点。

如何实现中序遍历

Golang中，我们可以使用递归或非递归的方式来实现中序遍历。

1. 递归方式：

递归实现中序遍历的思路是先遍历左子树，再访问根节点，最后遍历右子树。具体实现可以使用以下代码：

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

func inorderTraversal(root *TreeNode) []int {
    var res []int
    inorder(root, &res)
    return res
}

func inorder(root *TreeNode, res *[]int) {
    if root != nil {
        inorder(root.Left, res)
        *res = append(*res, root.Value)
        inorder(root.Right, res)
    }
}

2. 非递归方式：

非递归方式使用栈来实现中序遍历。首先将根节点入栈，然后进入一个循环，在循环中，将左子树中的所有节点都入栈，直到左子树为空。然后从栈中弹出一个节点，并访问它的值，接着将当前节点设置为弹出节点的右子树，重复上述操作，直到栈为空。

func inorderTraversal(root *TreeNode) []int {
    var res []int
    stack := []*TreeNode{}
    cur := root

    for cur != nil || len(stack) > 0 {
        if cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        } else {
            cur = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res = append(res, cur.Value)
            cur = cur.Right
        }
    }
    return res
}

中序遍历的应用

中序遍历不仅仅用于输出二叉搜索树的节点值，还可以用于判断两个二叉树是否相等、寻找二叉树中的众数、验证二叉搜索树等。下面是一个例子，演示了如何使用中序遍历来判断两个二叉树是否相等。

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }
    return p.Value == q.Value && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

对于给定的两个二叉树p和q，如果它们具有相同的根值，并且分别相等的左子树和右子树，则它们是相等的。通过中序遍历的递归方式，我们可以判断两个二叉树是否相等。

中序遍历是一种重要的树遍历方式，在Golang中的实现方式有递归和非递归两种。递归方式简洁明了，但在处理大型树时可能导致堆栈溢出。而非递归方式则通过使用栈来解决这个问题，并且能够有效地遍历树的所有节点。无论是哪种方式，中序遍历都可以应用于多种场景，包括输出节点值、判断两个二叉树是否相等等。