算法精粹(algorithm-essentials)

感谢soulmachine@github提供内容
二叉树是一个递归的数据结构,因此是一个用来考察递归思维能力的绝佳数据结构。

递归一定是深搜(见 [深搜与递归的区别](dfs-vs-recursion.md)),由于在二叉树上,递归的味道更浓些,因此本节用“二叉树的递归”作为标题,而不是“二叉树的深搜”,尽管本节所有的算法都属于深搜。

二叉树的先序、中序、后序遍历都可以看做是DFS,此外还有其他顺序的深度优先遍历,共有`3!=6`种。其他3种顺序是 `root->r->l,r->root->l, r->l->root`。