二叉树遍历
前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树
中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树
后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点
- 以根访问顺序决定是什么遍历
- 左子树都是优先右子树
递归遍历
前中后序递归遍历换换位置即可
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(result,root.Val) stack=append(stack,root) root=root.Left } // pop node:=stack[len(stack)-1] stack=stack[:len(stack)-1] root=node.Right } return result }
中序非递归
// 思路：通过stack 保存已经访问的元素，用于原路返回 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 { // 通过lastVisit标识右子节点是否已经弹出 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 == lastVisit { stack = stack[:len(stack)-1] // pop result = append(result, node.Val) // 标记当前这个节点已经弹出过 lastVisit = node } else { root = node.Right } } return result }
DFS 深搜-从上到下
func preorderTraversal(root *TreeNode) []int { result := make([]int, 0) dfs(root, &result) return result } func dfs(root *TreeNode, result *[]int) { if root == nil { return } *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) // 返回条件(null & leaf) if root == nil { return result } // 分治(Divide) left := divideAndConquer(root.Left) right := divideAndConquer(root.Right) // 合并结果(Conquer) result = append(result, root.Val) result = append(result, left...) result = append(result, right...) return result }
DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并
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) // 为什么要取length？ // 记录当前层有多少元素（遍历当前层，再添加下一层） l := len(queue) for i := 0; i < l; 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, list) } return result }
