144. 二叉树的遍历「前序、中序、后序」 Golang实现

题目描述：

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

思绪分析：

递归法：

1. 前序遍历的顺序是中左右的顺序。那么每个子树都是这个顺序，所以可以使用递归进行遍历。递归遍历有3部曲
2.         1.确定递归函数的参数和返回值。
3.                 因为返回值要求保存在一个数组中，所以递归函数的参数应该包括树的根节点和结果数组
4.                 ` func preOrder(root *TreeNode,res *[]int) `
5.         2.确定递归函数的终止条件
6.                 对于前序遍历来说，当某个根节点没有孩子节点的时候终止遍历。
7.                 ```
8.                 if root==nil {
9.                         return
10.                                  } ```
11.         3.确定单层递归的逻辑
12.                 按照顺序进行遍历即可。
13.            *res = append(*res, root.Val)
14.                         preOrder(root.Left,res)
15.                          preOrder(root.Right,res)

复制代码

最终的代码为：
点击检察代码

1. func preorderTraversal(root *TreeNode) []int {
2. //    递归函数3步骤：
3. //    1.确定递归函数的参数  2.确定递归函数的停止条件  3.确定单层递归的调用逻辑
4.    var res []int
5.    preOrder(root,&res)
6.    return res
7. }
9. func preOrder(root *TreeNode,res *[]int){
10.    if root==nil {
11.        return
12.    }
13.    *res = append(*res, root.Val)
14.    preOrder(root.Left,res)
15.    preOrder(root.Right,res)
16. }

复制代码

中序遍历：

点击检察代码

1. func inorderTraversal(root *TreeNode) []int {
2.    var res []int
3.    if root==nil{
4.        return res
5.    }
6.    getOrder(root,&res)
7.    return res
8. }
10. func getOrder(root *TreeNode, res *[]int)  {
11.    if root!=nil {
12.        getOrder(root.Left,res)
13.        *res = append(*res, root.Val)
14.        getOrder(root.Right,res)
15.    }
16. }

复制代码

后序遍历：

点击检察代码

1. func postorderTraversal(root *TreeNode) []int {
2.    var res []int
3.    postOrder(root,&res)
4.    return res
5. }
7. func postOrder(root *TreeNode,res *[]int)  {
8.    if root==nil{
9.        return
10.    }
11.    postOrder(root.Left,res)
12.    postOrder(root.Right,res)
13.    *res = append(*res, root.Val)
14. }

复制代码

非递归版本

上方是三种遍历的递归方式，肯定要明确递归的3个步骤。但是递归一般复杂度高，很难解决数据量大的数据。在盘算机中递归就是用栈实现的，所以我们可以用栈来实现递归函数的非递归版本。但是三种遍历方式的写法会有区别。
三种遍历的非递归实在都是从根节点开始按照根左右的方式入栈，区别就在于什么时候应该出栈。
前序遍历

前序遍历的次序是根左右，由于是栈来实现，所有实际的入栈次序是根右左，当访问到根的时候将根节点入栈--记载其值，然后将根节点出栈，按照根节点的右左孩子的次序入栈，再根据栈顶元素作为根节点进行处理。函数结束条件则是栈的长度大于0.
点击检察代码

1. func preorderTraversal(root *TreeNode) []int{
2.     var res []int
3.     if root==nil{
4.         return res
5.     }
6.     var stack []*TreeNode
7.     stack = append(stack, root)
8.     for len(stack)>0 {
9.         node:=stack[len(stack)-1]
10.         stack = stack[:len(stack)-1]
11.         if node!=nil {
12.             res = append(res, node.Val)
13.         }
14.         if node.Right != nil {
15.             stack = append(stack, node.Right)
16.         }
17.         if node.Left!=nil {
18.             stack = append(stack, node.Left)
19.         }
20.     }
21.     return res
22. }

复制代码

中序遍历

中序的遍历次序是左中右。
入栈次序：从根节点开始，首先将当前节点的左子树一路压入栈中，直到当前节点没有左子树为止。
出栈条件：当栈顶节点没有左子树时，出栈该节点并访问它，然后继续对其右子树进行遍历。
函数结束条件是  root!=nil || len(stack)>0 这是因为当遍历完左子树之后，回溯到整个树的root的时候，栈已经空了，但是右子树还没有入栈，所以还需要判断root是否为空。
点击检察代码

1. func inorderTraversal(root *TreeNode) []int{
2.     if root==nil {
3.         return []int{}
4.     }
5.     res,stack:=[]int{},[]*TreeNode{}
6.     for root!=nil || len(stack)>0 {
7.     //    先遍历左子树
8.         for root!=nil {
9.             stack = append(stack, root)
10.             root = root.Left
11.         }
12.     //    处理当前节点,最左下方的节点
13.         root = stack[len(stack)-1]
14.         stack = stack[:len(stack)-1]
15.         res = append(res, root.Val)
16.     //    遍历右子树
17.         root = root.Right
18.     }
19.     return res
20. }

复制代码

后序遍历

后序遍历的次序是：左-右-根。
入栈次序： 从根节点开始，首先将当前节点压入栈中，然后按照“左右”的次序将节点的左孩子和右孩子压入栈中。
出栈条件： 每次出栈栈顶元素后，仅在左右子树都已访问完成的情况下才访问根节点。为了包管这一点，通常需要借助一个额外的标记。所以我们通过pre指针来判断左右孩子是否已经访问过，只有他们都被访问过才能访问根节点。
因为入栈次序，所以栈顶元素必然是叶子节点，通过prev记载上一次访问的节点，如果当前节点是叶子节点，直接记载；若不是叶子节点，如果prev是当前节点的任一孩子，说明孩子节点访问完毕「2种情况，2个孩子和只有一个孩子，模拟一下便知」，则可以访问根节点了。
点击检察代码

1. func postorderTraversal(root *TreeNode) []int{
2.     if root==nil{
3.         return []int{}
4.     }
5.     res,stack := []int{},[]*TreeNode{}
6.     var prev *TreeNode
8.     stack = append(stack, root)
9.     for len(stack)>0{
10.         current:=stack[len(stack)-1]
11.     if(current.Left== nil && current.Right ==nil) || (prev!=nil && (prev == current.Left || prev==current.Right)){
12.         res = append(res, current.Val)
13.         stack = stack[:len(stack)-1]
14.         prev = current
15.     }else{
16.         if current.Right!=nil {
17.             stack = append(stack, current.Right)
18.         }
19.         if current.Left != nil {
20.             stack = append(stack, current.Left)
21.         }
22.     }
23.     }
24.     return res
25. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。