简介

二叉树是一个递归的数据结构，因此是一个用来考察递归思维能力的绝佳数据结构。

递归一定是深搜（见 深搜与递归的区别），由于在二叉树上，递归的味道更浓些，因此本节用“二叉树的递归”作为标题，而不是“二叉树的深搜”，尽管本节所有的算法都属于深搜。

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