golang 反向遍历二叉树

admin

0
文章

0
评论

2025-03-19 15:53:30 编程来源：ZONE.CI 全球网 0 阅读模式

反向遍历二叉树的实现

在Golang开发中，遍历二叉树是一个常见的需求。而对于反向遍历二叉树，我们可以采用递归或栈的方式来实现。

递归实现反向遍历二叉树

使用递归来实现反向遍历二叉树相对简单。我们可以通过递归地遍历右子树、根节点和左子树的顺序来完成反向遍历。

具体实现如下：


func reverseTraverse(node *Node) {
    if node == nil {
        return
    }
    
    reverseTraverse(node.right)
    fmt.Println(node.value)
    reverseTraverse(node.left)
}

在这段代码中，我们首先判断当前节点是否为空，如果为空则直接返回。接着，我们递归调用函数来遍历右子树，然后打印当前节点的值，最后再递归调用来遍历左子树。

栈实现反向遍历二叉树

除了使用递归实现外，我们还可以使用栈来实现反向遍历二叉树。这种方法相对复杂一些，但是可以避免使用大量的堆栈空间。

具体实现如下：


func reverseTraverse(node *Node) {
    if node == nil {
        return
    }
    
    stack := []*Node{node}
    var result []int
    
    for len(stack) > 0 {
        // 获取栈顶节点
        curr := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        
        result = append(result, curr.value)
        
        // 将右子树加入栈中
        if curr.right != nil {
            stack = append(stack, curr.right)
        }
        
        // 将左子树加入栈中
        if curr.left != nil {
            stack = append(stack, curr.left)
        }
    }
    
    // 反向打印结果
    for i := len(result) - 1; i >= 0; i-- {
        fmt.Println(result[i])
    }
}

这段代码中，我们首先创建一个栈，并将根节点压入栈中。然后，我们利用循环不断从栈中取出节点，打印节点的值，并将右子树和左子树分别压入栈中。最后，我们通过遍历结果数组，反向输出结果。