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

前言

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

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

首先定义二叉树结构

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

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

type TreeNodeWrapper struct {
	Node *TreeNode
	Visited bool
}

然后先写最难的后序遍历

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) // 1
				if node.Node.Right != nil {
					stack = append(stack, &TreeNodeWrapper{node.Node.Right, false}) // 2
				}
				if node.Node.Left != nil {
					stack = append(stack, &TreeNodeWrapper{node.Node.Left, false}) // 3
				}
			} else {
				res = append(res,node.Node.Val)
			}
		}
	}
	return res
}

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

• 前序遍历

  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
  }

• 中序遍历

  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
  }