二叉树 前/中/后/层 四种方式遍历递归实现

  二叉树的遍历，无论是在leetcode刷题或者面试过程中，都是十分常见，重要性无需赘述。本文将采用Golang语言来实现前/中/后/层四种遍历方式。

二叉树定义

// 二叉树节点定义
type TreeNode struct {
    Val   int
    Left  *TreeNode  // 左子树
    Right *TreeNode // 右子树
}

二叉树样例

一. 前序遍历

• 1. 遍历顺序
       中 -> 左 -> 右。
• 2. 代码实现

// 前序遍历
func PreOrderTraversal(tree *TreeNode) {
    if tree == nil {
        return
    }

    fmt.Printf(" %d -> ", tree.Val)
    PreOrderTraversal(tree.Left)
    PreOrderTraversal(tree.Right)
}

• 3. 结果输出
     1 -> 2 -> 4 -> 3 -> 5 -> 6 ->

二. 中序遍历

• 1. 遍历顺序
       左 -> 中 -> 右。
• 2. 代码实现

// 中序遍历
func MidOrderTraversal(tree *TreeNode) {
    if tree == nil {
        return
    }

    MidOrderTraversal(tree.Left)
    fmt.Printf(" %d -> ", tree.Val)
    MidOrderTraversal(tree.Right)
}

• 3. 结果输出
     4 -> 2 -> 1 -> 5 -> 3 -> 6 ->

三. 后序遍历

• 1. 遍历顺序
       左 -> 右 -> 中。
• 2. 代码实现

// 后序遍历
func PostOrderTraversal(tree *TreeNode) {
    if tree == nil {
        return
    }

    PostOrderTraversal(tree.Left)
    PostOrderTraversal(tree.Right)
    fmt.Printf(" %d -> ", tree.Val)
}

• 3. 结果输出
     4 -> 2 -> 5 -> 6 -> 3 -> 1 ->

四. 按层遍历

• 1. 遍历顺序
       层。
• 2. 代码实现

// 按层遍历

func LevelOrderTraversal(tree *TreeNode) {
    if tree == nil {
        return
    }

    // 采用队列实现
    queue := make([]*TreeNode, 0)
    queue = append(queue, tree) // queue push
    for len(queue) > 0 {
        tree = queue[0]
        fmt.Printf(" %d -> ", tree.Val)

        queue = queue[1:] // queue pop

        if tree.Left != nil {
            queue = append(queue, tree.Left)
        }
        if tree.Right != nil {
            queue = append(queue, tree.Right)
        }
    }
}

• 3. 结果输出
     1 -> 2 -> 3 -> 4 -> 5 -> 6 ->