前序遍历 根左右 后序遍历 左根右 后序遍历 左右根
前序递归
func preorderTraversal(root *TreeNode) { if root==nil{ return } fmt.Println(root.val) preorderTraversal(root.Left) preorderTraversal(root.Right) }前序非递归
func preorderTraversal(root *TreeNode) []int { if root == nil{ return nil } result:=make([]int,0) stack:=make([]TreeNode,0) for root!=nil||len(stack)!=0{ for root!=nil { result=append(rusult,root.Val) stack=append(stack,root) root=root.Left } node:=stack[len(stack)-1] stack=stack[:len(stack)-1] root=node.Right } return result }中序非递归
func inorderTraversal(root *TreeNode) []int{ result := make([]int,0) if root == nil{ return result } stack := make([]*TreeNode,0) for len(stack) > 0 || root != nil{ for root != nil{ stack = append(stack,root) root = root.Left } val := stack[len(stack)-1] stack = stack[:len(stack)-1] result = append(result,val.Val) root = val.Right } return result }后序非递归
func postorderTraversal(root *TreeNode) []int{ if root == nil{ return nil } result := make([]int,0) stack :=make([]*TreeNode,0) var lastVisit *TreeNode for root != nil || len(stack) != 0 { for root != nil{ stack = append(stack,root) root = root.Left } node := stack[len(stack)-1] if node.Right == nil || node.Right == last Visit{ stack = stack[:len(stack)-1] result = append(result,node.Val) lastVisit = node } else{ root = node.Right } } return result }DFS深度搜索-从上到下
type TreeNode struct{ Val int Left *TreeNode Right *TreeNode } func preorderTraversal(root *TreeNode)int[]{ result := make([]int,0) dfs(root,&result) return result } func dfs(root *TreeNode,rusult *[]int){ if root == nil{ ruturn } *result = append(*result,root.Val) dfs(root.Left,result) dfs(root.Right,result) }DFS深度搜索-从上到下（分治法）
func preorderTraversal(root *TreeNode)[]int{ result := divideAndConquer(root) return result } func divideAndConquer(root *TreeNode)[]int{ result := make([]int,0) if root == nil{ return result } left := divideAndConquer(root.Left) right := divideAndConquer(root.Right) result = append(result,root.Val) result = append(result,left...) result = append(result,right...) return result }BFS层次遍历
func levelOrder(root *TreeNode)[][]int{ result := make([][]int,0) if root == nil{ return result } queue := make([]*TreeNode,0) queue = append(queue,root) for len(queue) > 0{ list := make([]int,0) l := len(queue) for i := 0; i < 1; i++{ level := queue[0] queue = queue[1:] list = append(list,level.Val) if level.Left != nil{ queue = append(queue,level.Left) } if level.Right != nil{ queue = append(queue,level.Right) } } result = append(result，lsit) } return result }