深度优先遍历(DFS)_广度优先遍历(BFS)

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

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

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

//递归的核心就是dfs函数，拿前序遍历来说 根——左——右 循环调用递归调用dfs函数

func dfs(root *TreeNode,res [] int){
    if root == nil {
        return
    }
    res = append(res,root.value)
    dfs(root.left,res)
    dfs(root.right,res)
}

​

非递归方法：

//非递归的方法，是用栈实现 由于栈是'先进后出'的顺序 也是拿前序遍历来说
//1.初始化栈，并将根节点入栈，当栈不为空的时候，弹栈入结果集
//2.右子树加入栈
//3.左子树加入栈
func dfs(root *TreeNode) []int{
    stack := []TreeNode{}
    res := []int
    if root == nil {
        return res
    }
    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.value)
            if node.right != nil {
                stack = append(stack,node.right)
            }
            if node.left != nil {
                stack = append(stack,node.left)
            }
        }
    }
    return res
}

//模板化的前中后序遍历, 套路是 第一步永远是将左子树都放到栈里，之后弹出之后再计算右子树，根据前中后顺序不同选择不同的位置放入结果集

//前序
func dfs(root *TreeNode) []int {
	stack := []*TreeNode{}
    res := []int
    if root == nil {
        return res
    }
	for len(stack) != 0 {
		for root != nil {
            res = append(res, root.Val)
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		root = root.Right
	}
	return
}

//中序
func dfs(root *TreeNode) []int {
	stack := []*TreeNode{}
    res := []int
    if root == nil {
        return res
    }
	for 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
}

//后序 
func dfs(root *TreeNode) []int {
	stack := []*TreeNode{}
    var prev *TreeNode
    res := []int
    if root == nil {
        return res
    }
	for len(stack) != 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if root.Right == nil || root.Right == prev {
            res = append(res, root.Val)
            prev = root
            root = nil
        } else {
            stk = append(stk, root)
            root = root.Right
        }
	}
	return res
}

​

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

func bfs(root *TreeNode) [][]int {
    ret := [][]int{}
    if root == nil {
        return ret
    }
    q := []*TreeNode{root}
    for i := 0; len(q) > 0; i++ {
        ret = append(ret, []int{})
        p := []*TreeNode{}
        for j := 0; j < len(q); j++ {
            node := q[j]
            ret[i] = append(ret[i], node.Val)
            if node.Left != nil {
                p = append(p, node.Left)
            }
            if node.Right != nil {
                p = append(p, node.Right)
            }
        }
        q = p
    }
    return ret
}