跳到主要内容

简介

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

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

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