深度优先遍历：按照根节点相对于左右子节点的访问先后来划分

前序 Pre-Order Traversal: 先访问根结点 再访问子树

中序 In-Order Traversal: 先访问左(右)子树，再访问根结点，最后访问右(左)子树

后序 Post-Order Traversal: 先访问子树，再访问根结点

快速排序是二叉树的前序遍历

快速排序的逻辑是，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序

func quickSort(nums []int, low, high int) {
	// 前序遍历位置
	p := partition(nums, low, high) // 通过交换元素构建分界点 p
	quickSort(nums, low, p-1)
	quickSort(nums, p+1, high)
}

归并排序是二叉树的后序遍历

归并排序的逻辑，若要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并

func mergeSort(nums []int, low, high int) {
	mid := (low + high) / 2
	mergeSort(nums, low, mid)
	mergeSort(nums, mid+1, high)
	// 后序遍历位置 合并两个排好序的子数组
	merge(nums, low, mid, high)
}

只要涉及递归，都可以抽象成二叉树的问题

我们先把题目要求细化，搞清楚 root 结点应该做什么，最后交给前/中/后序遍历框架，不要跳进递归细节

226. Invert Binary Tree

		 4
   /   \\
  2     7
 / \\   / \\
1   3 6   9

关键思路在于我们发现翻转整棵树就是交换每个结点的左右子结点，于是把交换的逻辑放在前/后序遍历的位置。二叉树的问题要细化成每个结点需要做的子操作

func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	// 前序遍历位置 交换左右子结点
	tmp := root.Left
	root.Left = root.Right
	root.Right = tmp
	
	invertTree(root.Left)
	invertTree(root.Right)

	return root
}

116. Populating Next Right Pointers in Each Node