二叉树的前中后序遍历（迭代法）（含leetcode上三道【前中后序】遍历题目）

文章目录

前序遍历（迭代法）
中序遍历（迭代法）
后序遍历（迭代法）
总结

为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？

在队列与栈专题我们就感受到了，匹配问题都是栈的强项，而递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，这就是递归为什么可以返回上一层位置的原因。

此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。

前序遍历（迭代法）

我们先看一下前序遍历。

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

为什么要先加入右孩子，再加入左孩子呢？因为这样出栈的时候才是中左右的顺序。

不难写出如下Go代码: （注意代码中空节点不入栈）

144. 二叉树的前序遍历

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

    res := make([]int,0)
    // 二叉树的遍历（迭代法）依赖栈来辅助完成
    stack := make([]*TreeNode,0)
    stack = append(stack,root)
    // 初始时根节点已经入栈，后续栈不为空就可以一直遍历
    for len(stack) != 0 {
        // 栈弹出一个元素加入结果中
        curNode := stack[len(stack) - 1]
        stack = stack[0:len(stack) - 1]
        res = append(res,curNode.Val)
        // 先让右节点入栈，后让左节点入栈，这样出栈才会符合根左右
        if curNode.Right != nil {
            stack = append(stack,curNode.Right)
        }

        if curNode.Left != nil {
            stack = append(stack,curNode.Left)
        }

    }

    return res
}

在这里插入图片描述

此时会发现貌似使用迭代法写出前序遍历并不难，确实不难。

此时是不是想改一点前序遍历代码顺序就把中序遍历搞出来了？

其实还真不行！

但接下来，再用迭代法写中序遍历的时候，会发现套路又不一样了，目前的前序遍历的逻辑无法直接应用到中序遍历上。

中序遍历（迭代法）

为了解释清楚，我说明一下刚刚在迭代的过程中，其实我们有两个操作：

处理：将元素放进res数组中
访问：遍历节点

分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是再把节点的数值放进res数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，当前指针向左边走到头的时候，说明左边遍历到底了，可以从栈弹出一个元素，即【左中右】，左边到底，栈中弹出【中】访问，而后遍历【右】，但是【右】又是一颗子树，继续往左走到头才行。

中序遍历，可以写出如下Go代码：

注意体会下面注释中的【遍历】和【访问】的区别

94. 二叉树的中序遍历

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

    res := make([]int,0)
    stack := make([]*TreeNode,0)
    cur := root
    
    // 注意体会下面注释中的【遍历】和【访问】的区别
    for cur != nil || len(stack) != 0 {
        // 当前节点不为nil，说明左边没有走到头，继续往左遍历
        if cur != nil {
            stack = append(stack,cur)
            cur = cur.Left
        } else { // 当前节点为空还能来到这里，说明栈非空，栈顶就是当前要访问的元素
            cur = stack[len(stack) - 1]
            stack = stack[0:len(stack) - 1]
            // 当前访问的元素放入结果
            res = append(res,cur.Val)
            // 当前节点左边遍历完，当前节点也访问过了，即左中以完成，接下来访问当前节点的右子树
            cur = cur.Right
        }
    }
    
    return res
}

在这里插入图片描述

后序遍历（迭代法）

再来看后序遍历，先序遍历是中左右，后序遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转res数组，输出的结果顺序就是左右中了，如下图：
在这里插入图片描述

所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：

145. 二叉树的后序遍历

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

    res := make([]int,0)
    stack := make([]*TreeNode,0)
    stack = append(stack,root)
    for len(stack) != 0 {
        cur := stack[len(stack) - 1]
        stack = stack[0:len(stack) - 1]
        res = append(res,cur.Val)

        if cur.Left != nil {
            stack = append(stack,cur.Left)
        }
        if cur.Right != nil {
            stack = append(stack,cur.Right)
        }
    }

   // 反转遍历的结果
    reverse(res)

    return res
}

func reverse(arr []int) {

    i,j := 0,len(arr) - 1
    for i < j {
        arr[i],arr[j] = arr[j],arr[i]
        i++
        j--
    }

    return
}