当前位置：首页 > news >正文

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

news 来源：原创 2024/9/20 9:44:54

文章目录

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

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

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

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

前序遍历（迭代法）

我们先看一下前序遍历。

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

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

不难写出如下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) - 1for i < j {arr[i],arr[j] = arr[j],arr[i]i++j--}return
}