标题描绘：

给你二叉树的根节点 root ，回来它节点值的 前序 遍历。

思路剖析：

递归法：

前序遍历的次序是中左右的次序。那么每个子树都是这个次序，所以能够运用递归进行遍历。递归遍历有3部曲
	1.确认递归函数的参数和回来值。
		由于回来值要求保存在一个数组中，所以递归函数的参数应该包含树的根节点和成果数组
		` func preOrder(root *TreeNode,res *[]int) `
	2.确认递归函数的中止条件
		关于前序遍历来说，当某个根节点没有孩子节点的时分中止遍历。
		```
		if root==nil {
                	return
				 } ```
	3.确认单层递归的逻辑
		依照次序进行遍历即可。
	   *res = append(*res, root.Val)
			preOrder(root.Left,res)
			 preOrder(root.Right,res)

终究的代码为：

func preorderTraversal(root *TreeNode) []int {
//    递归函数3过程：
//    1.确认递归函数的参数  2.确认递归函数的中止条件  3.确认单层递归的调用逻辑
   var res []int
   preOrder(root,&res)
   return res
}

func preOrder(root *TreeNode,res *[]int){
   if root==nil {
       return
   }
   *res = append(*res, root.Val)
   preOrder(root.Left,res)
   preOrder(root.Right,res)
}

中序遍历：

func inorderTraversal(root *TreeNode) []int {
   var res []int
   if root==nil{
       return res
   }
   getOrder(root,&res)
   return res
}

func getOrder(root *TreeNode, res *[]int)  {
   if root!=nil {
       getOrder(root.Left,res)
       *res = append(*res, root.Val)
       getOrder(root.Right,res)
   }
}

后序遍历：

func postorderTraversal(root *TreeNode) []int {
   var res []int
   postOrder(root,&res)
   return res
}

func postOrder(root *TreeNode,res *[]int)  {
   if root==nil{
       return
   }
   postOrder(root.Left,res)
   postOrder(root.Right,res)
   *res = append(*res, root.Val)
}

非递归版别

上方是三种遍历的递归方法，一定要清晰递归的3个过程。可是递归一般复杂度高，很难处理数据量大的数据。在计算机中递归便是用栈完结的，所以咱们能够用栈来完结递归函数的非递归版别。可是三种遍历方法的写法会有差异。

三种遍历的非递归其实都是从根节点开端依照根左右的方法入栈，差异就在于什么时分应该出栈。

前序遍历

前序遍历的次序是根左右，由所以栈来完结，一切实践的入栈次序是根右左，当拜访到根的时分将根节点入栈--记载其值，然后将根节点出栈，依照根节点的右左孩子的次序入栈，再依据栈顶元素作为根节点进行处理。函数结束条件则是栈的长度大于0.

func preorderTraversal(root *TreeNode) []int{
    var res []int
    if root==nil{
        return res
    }
    var stack []*TreeNode
    stack = append(stack, root)
    for len(stack)>0 {
        node:=stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if node!=nil {
            res = append(res, node.Val)
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left!=nil {
            stack = append(stack, node.Left)
        }
    }
    return res
}

中序遍历

中序的遍历次序是左中右。
入栈次序：从根节点开端，首先将当时节点的左子树一路压入栈中，直到当时节点没有左子树停止。
出栈条件：当栈顶节点没有左子树时，出栈该节点并拜访它，然后持续对其右子树进行遍历。

函数结束条件是 root!=nil || len(stack)>0 这是由于当遍历完左子树之后，回溯到整个树的root的时分，栈现已空了，可是右子树还没有入栈，所以还需求判别root是否为空。

func inorderTraversal(root *TreeNode) []int{
    if root==nil {
        return []int{}
    }
    res,stack:=[]int{},[]*TreeNode{}
    for root!=nil || len(stack)>0 {
    //    先遍历左子树
        for root!=nil {
            stack = append(stack, root)
            root = root.Left
        }
    //    处理当时节点,最左下方的节点
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, root.Val)
    //    遍历右子树
        root = root.Right
    }
    return res
}

后序遍历

后序遍历的次序是：左-右-根。
入栈次序： 从根节点开端，首先将当时节点压入栈中，然后依照“左右”的次序将节点的左孩子和右孩子压入栈中。
出栈条件： 每次出栈栈顶元素后，仅在左右子树都已拜访完结的状况下才拜访根节点。为了确保这一点，一般需求凭借一个额定的符号。所以咱们经过pre指针来判别左右孩子是否现已拜访过，只要他们都被拜访过才干拜访根节点。
由于入栈次序，所以栈顶元素必定是叶子节点，经过prev记载上一次拜访的节点，假如当时节点是叶子节点，直接记载；若不是叶子节点，假如prev是当时节点的任一孩子，阐明孩子节点拜访结束「2种状况，2个孩子和只要一个孩子，模仿一下便知」，则能够拜访根节点了。

func postorderTraversal(root *TreeNode) []int{
    if root==nil{
        return []int{}
    }
    res,stack := []int{},[]*TreeNode{}
    var prev *TreeNode

    stack = append(stack, root)
    for len(stack)>0{
        current:=stack[len(stack)-1]
    if(current.Left== nil && current.Right ==nil) || (prev!=nil && (prev == current.Left || prev==current.Right)){
        res = append(res, current.Val)
        stack = stack[:len(stack)-1]
        prev = current
    }else{
        if current.Right!=nil {
            stack = append(stack, current.Right)
        }
        if current.Left != nil {
            stack = append(stack, current.Left)
        }
    }
    }
    return res
}