前言

​ 二叉树的遍历，从编程方式上来说主要有两种写法，一种是递归的写法，一种是非递归的写法，其中递归的写法很容易，在leetcode上都是属于easy级别的题目，风格也非常一致，学会了前序遍历，调整一下代码顺序，几秒之内中序、后序遍历就都可以写出来了。但是非递归的写法则不然，市面上包括很多教科书上二叉树前、中、后序的非递归遍历的写法都不一样，在leetcode上非递归的写法也基本都是属于medium级别的，其中后序遍历属于hard级别的，本文主要是介绍一种二叉树非递归遍历的统一写法，可以帮助你像写递归遍历那样，只要调整一下代码顺序就可以很快写好前、中、后序非递归遍历。

二叉树非递归遍历的一种统一写法

首先定义二叉树结构

1
2
3
4
5

type TreeNode struct {
     Val int
     Left *TreeNode
     Right *TreeNode
}

然后对二叉树节点进行一次Wrapper, 增加一个字段标示这个节点的访问状态，这个方法我也叫它为节点标记法（雾

1
2
3
4

type TreeNodeWrapper struct {
	Node *TreeNode
	Visited bool
}

然后先写最难的后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func postorderTraversal(root *TreeNode) []int {
	res := make([]int,0)
	if root == nil {
		return res
	}
	stack := make([]*TreeNodeWrapper,0)
	stack = append(stack,&TreeNodeWrapper{root,false})
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if node != nil {
			if !node.Visited {
				node.Visited = true
				stack = append(stack, node) 
				if node.Node.Right != nil {
					stack = append(stack, &TreeNodeWrapper{node.Node.Right, false}) 
				}
				if node.Node.Left != nil {
					stack = append(stack, &TreeNodeWrapper{node.Node.Left, false}) 
				}
			} else {
				res = append(res,node.Node.Val)
			}
		}
	}
	return res
}

主要需要关注的就是注释1、2、3的地方,由于后序遍历的顺序是左-右-根，所以入栈的顺序就是根-右-左。以此类推，前序遍历的非递归写法调整对应代码的顺序就是2-3-1，中序则是2-1-3，完整代码如下：

• 前序遍历

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

  func preorderTraversal(root *TreeNode) []int { res := make([]int,0) if root == nil { return res } stack := make([]*TreeNodeWrapper,0) stack = append(stack,&TreeNodeWrapper{root,false}) for len(stack) > 0 { node := stack[len(stack)-1] stack = stack[:len(stack)-1] if node != nil { if !node.Visited { if node.Node.Right != nil { stack = append(stack, &TreeNodeWrapper{node.Node.Right, false}) } if node.Node.Left != nil { stack = append(stack, &TreeNodeWrapper{node.Node.Left, false}) } node.Visited = true stack = append(stack, node) } else { res = append(res,node.Node.Val) } } } return res }

• 中序遍历

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

  func inorderTraversal(root *TreeNode) []int { res := make([]int,0) if root == nil { return res } stack := make([]*TreeNodeWrapper,0) stack = append(stack,&TreeNodeWrapper{root,false}) for len(stack) > 0 { node := stack[len(stack)-1] stack = stack[:len(stack)-1] if node != nil { if !node.Visited { if node.Node.Right != nil { stack = append(stack, &TreeNodeWrapper{node.Node.Right, false}) } node.Visited = true stack = append(stack, node) if node.Node.Left != nil { stack = append(stack, &TreeNodeWrapper{node.Node.Left, false}) } } else { res = append(res,node.Node.Val) } } } return res }