二叉树的遍历

前言

树的遍历也叫树的搜索，是指按照某种规律对树的节点进行一遍不重复的访问。按照不同的方式，可以分为：树的前序遍历、中序遍历、后序遍历和层序遍历。

前序遍历

1. 树的前序遍历
   树的前序遍历指的是对树按照 根、左、右 的规律进行访问。
   
   遍历结果为：F, B, A, D, C, E, G , I, H

2. 递归代码实现

func preorderTraversal(root *TreeNode) {
	if root == nil {
		return nil
	}
	fmt.Printf("%d, ", root.Val)
	inorderTraversal(root.Left)
	inorderTraversal(root.Right)
}

中序遍历

1. 树的中序遍历
   树的中序遍历指的是对树按照 左、根、右 的规律进行访问。
   
   遍历结果为：A, B, C, D, E, F, G, H, I

2. 递归代码实现

func inorderTraversal(root *TreeNode) {
	if root == nil {
		return nil
	}
	inorderTraversal(root.Left)
	fmt.Printf("%d, ", root.Val)
	inorderTraversal(root.Right)
}

后序遍历

1. 树的后序遍历
   树的后序遍历指的是对树按照 左、右、根 的规律进行访问。
   
   遍历结果为：A, C, E, D, B, H, I, G, F

2. 递归代码实现

func postorderTraversal(root *TreeNode) {
	if root == nil {
		return nil
	}
	inorderTraversal(root.Left)
	inorderTraversal(root.Right)
    fmt.Printf("%d, ", root.Val)
}

层序遍历

1. 树的层序遍历
   树的层序遍历就是从上到下，从左到右输出节点
   
   遍历结果为： F, B, G, A, D, I, C, E, H

2. 迭代代码（把每一层放在一个数组中，最后将它们再放入一个总的数组中）

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	var res [][]int     // 保存每层节点
	queue := newQueue() // 使用队列保存
	queue.offer(root)
	for !queue.isEmpty() {
		var ans []int // 当前层元素值
		sz := queue.len()
		for sz > 0 {
			// 弹出栈顶元素
			top := queue.pop()
			ans = append(ans, top.Val)
			if top.Left != nil {
				queue.offer(top.Left)
			}
			if top.Right != nil {
				queue.offer(top.Right)
			}
			sz--
		}
		res = append(res, ans)
	}
	return res
}