介绍

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。

上图的树的前序遍历顺序：

1->2->4->5->7->8->3->6->9

中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。

上图的树的前序遍历顺序：

4->2->7->5->8->3->9->6

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

上图的树的前序遍历顺序：

4->7->8->5->2->9->6->3->1

总结

对于前中后序遍历，这个“序”，只针对于根节点，即前序先访问根节点，中序中间访问，后序最后访问，对于左右节点，永远是先左节点后右节点。

Golang实现（递归法）

Leetcode

前序遍历：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

中序遍历：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

后序遍历：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

前序遍历

package leetcode

// TreeNode Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func preorderTraversal(root *TreeNode) []int {
    var list []int
    preorder(root, &list)
    return list
}

func preorder(node *TreeNode, list *[]int) {
    if node == nil {
        return
    }
    *list = append(*list, node.Val)
    preorder(node.Left, list)
    preorder(node.Right, list)
}

中序遍历

package leetcode

// TreeNode Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

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

func inorder(node *TreeNode, list *[]int) {
    if node == nil {
        return
    }
    inorder(node.Left, list)
    *list = append(*list, node.Val)
    inorder(node.Right, list)
}

后续遍历

package leetcode

// TreeNode Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func postorderTraversal(root *TreeNode) []int {
    var list []int
    postorder(root, &list)
    return list
}

func postorder(node *TreeNode, list *[]int) {
    if node == nil {
        return
    }
    postorder(node.Left, list)
    postorder(node.Right, list)
    *list = append(*list, node.Val)
}