数据结构与算法笔记--二叉树的前中后序遍历

一、前序遍历

基于Leetcode

1、递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    var vals []int

    var preorder func(*TreeNode)
    preorder = func (node *TreeNode) {
        if node == nil {
            return
        }

        vals = append(vals, node.Val)
        preorder(node.Left)
        preorder(node.Right)
    }

    preorder(root)
    return vals
}

2、迭代

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    var vals []int
    stack, node := []*TreeNode{}, root // 迭代借助栈实现

    for node != nil || len(stack) > 0 {
        for node != nil { // 一直向左遍历，同时记录值和节点。记录节点是记录路径，为了后续继续遍历右节点
            vals = append(vals, node.Val)
            stack = append(stack, node)
            node = node.Left
        }

		// 继续遍历右子树
        node = stack[len(stack)-1].Right
        stack = stack[:len(stack)-1]
    }
    
    return vals
}

二、中序遍历

1、递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    var vals []int

    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        inorder(node.Left)
        vals = append(vals, node.Val)
        inorder(node.Right)
    }

    inorder(root)
    return vals
}

2、迭代

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    var vals []int
    stack, node := []*TreeNode{}, root
    for node != nil || len(stack) > 0 {
        for node != nil {
            stack = append(stack, node)
            node = node.Left
        }

        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        vals = append(vals, node.Val)
        node = node.Right
    }
    
    return vals
}

三、后序遍历

1、递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    var vals []int

    var postorder func(*TreeNode)
    postorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        postorder(node.Left)
        postorder(node.Right)
        vals = append(vals, node.Val)
    }

    postorder(root)
    return vals
}

2、迭代

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    var vals []int
    var prev *TreeNode

    stack, node := []*TreeNode{}, root
    for node != nil || len(stack) > 0 {
        for node != nil {
            stack = append(stack, node)
            node = node.Left
        }

        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        
        if node.Right == nil || node.Right == prev { // 右子树为空或者已经遍历过，那么遍历当前节点
            vals = append(vals, node.Val)
            prev = node
            node = nil
        } else { // 右子树不为空并且没有遍历过，则继续遍历右子树
            stack = append(stack, node)
            node = node.Right
        }
    }

    return vals
}