深度优先遍历（DFS）:
    核心思想就是 “一条路走道黑”，从一个位置，一般是二叉树的顶点开始，一直向下走，走道不能走了之后 回到上一个节点，看能否还有其他的路 （回溯法），直到遍历完成

    实现：递归方法 和 非递归方法

    递归方法：（比较简单，但是深度较深的时候，会导致内存溢出）

    1. //递归的核心就是dfs函数，拿前序遍历来说 根——左——右 循环调用递归调用dfs函数
    3. func dfs(root *TreeNode,res [] int){
    4.     if root == nil {
    5.         return
    6.     }
    7.     res = append(res,root.value)
    8.     dfs(root.left,res)
    9.     dfs(root.right,res)
    10. }

    非递归方法：

    1. //非递归的方法，是用栈实现 由于栈是'先进后出'的顺序 也是拿前序遍历来说
    2. //1.初始化栈，并将根节点入栈，当栈不为空的时候，弹栈入结果集
    3. //2.右子树加入栈
    4. //3.左子树加入栈
    5. func dfs(root *TreeNode) []int{
    6.     stack := []TreeNode{}
    7.     res := []int
    8.     if root == nil {
    9.         return res
    10.     }
    11.     stack = append(stack,root)
    12.     for len(stack)!= 0 {
    13.         node := stack[len(stack)-1]
    14.         stack = stack[:len(stack)-1]
    15.         if node!=nil {
    16.             res = append(res,node.value)
    17.             if node.right != nil {
    18.                 stack = append(stack,node.right)
    19.             }
    20.             if node.left != nil {
    21.                 stack = append(stack,node.left)
    22.             }
    23.         }
    24.     }
    25.     return res
    26. }
    28. //模板化的前中后序遍历, 套路是 第一步永远是将左子树都放到栈里，之后弹出之后再计算右子树，根据前中后顺序不同选择不同的位置放入结果集
    30. //前序
    31. func dfs(root *TreeNode) []int {
    32.     stack := []*TreeNode{}
    33.     res := []int
    34.     if root == nil {
    35.         return res
    36.     }
    37.     for len(stack) != 0 {
    38.         for root != nil {
    39.             res = append(res, root.Val)
    40.             stack = append(stack, root)
    41.             root = root.Left
    42.         }
    43.         root = stack[len(stack)-1]
    44.         stack = stack[:len(stack)-1]
    45.         root = root.Right
    46.     }
    47.     return
    48. }
    50. //中序
    51. func dfs(root *TreeNode) []int {
    52.     stack := []*TreeNode{}
    53.     res := []int
    54.     if root == nil {
    55.         return res
    56.     }
    57.     for len(stack) != 0 {
    58.         for root != nil {
    59.             stack = append(stack, root)
    60.             root = root.Left
    61.         }
    62.         root = stack[len(stack)-1]
    63.         stack = stack[:len(stack)-1]
    64.         res = append(res, root.Val)
    65.         root = root.Right
    66.     }
    67.     return res
    68. }
    70. //后序 
    71. func dfs(root *TreeNode) []int {
    72.     stack := []*TreeNode{}
    73.     var prev *TreeNode
    74.     res := []int
    75.     if root == nil {
    76.         return res
    77.     }
    78.     for len(stack) != 0 {
    79.         for root != nil {
    80.             stack = append(stack, root)
    81.             root = root.Left
    82.         }
    83.         root = stack[len(stack)-1]
    84.         stack = stack[:len(stack)-1]
    85.         if root.Right == nil || root.Right == prev {
    86.             res = append(res, root.Val)
    87.             prev = root
    88.             root = nil
    89.         } else {
    90.             stk = append(stk, root)
    91.             root = root.Right
    92.         }
    93.     }
    94.     return res
    95. }

    深度优先遍历（DFS）:
    核心思想就是分层次遍历，用队列存储树的每一层，这样遍历这个队列，安层次输出到二维数据中去

    1. func bfs(root *TreeNode) [][]int {
    2.     ret := [][]int{}
    3.     if root == nil {
    4.         return ret
    5.     }
    6.     q := []*TreeNode{root}
    7.     for i := 0; len(q) > 0; i++ {
    8.         ret = append(ret, []int{})
    9.         p := []*TreeNode{}
    10.         for j := 0; j < len(q); j++ {
    11.             node := q[j]
    12.             ret[i] = append(ret[i], node.Val)
    13.             if node.Left != nil {
    14.                 p = append(p, node.Left)
    15.             }
    16.             if node.Right != nil {
    17.                 p = append(p, node.Right)
    18.             }
    19.         }
    20.         q = p
    21.     }
    22.     return ret
    23. }