如果中序遍历为有序的话则为二叉搜索树，为了避免退化为单链表

如果中序遍历为有序的话则为二叉搜索树，为了避免退化为单链表，加入平衡规则后保持平衡则为平衡二叉树，搜索的时间复杂度为O(lgn).

满二叉树、完全二叉树又推出最大堆、最小堆（堆排序、定时器）。平衡二叉树又推出avl、红黑树。

对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

广度优先搜索，需要使用队列来实现，和迭代类似，也是要让根节点先入，根节点弹出队列前，要把左右子节点入队列。

求最优解问题、且子问题的解有重叠（某个节点的解是其父节点的一部分），需要找到状态转移方程。

从二叉树的节点A出发，可以向上或向下走，但沿途的节点只能经过一次，当达到节点B时，路径上的节点树叫做A到B到距离。

这棵树的最大距离（首先构建出这个模型，和高中的受力分析意义画出图来）：max(左子树的最大距离，右子树的最大距离，左子树的高度+右子树的高度+1)

子问题的解有重叠：f(n-1)是f(n)解的一部分，确定边界值为某个叶子节点的解为f(0)=max(0 0 1)=1。

欢迎您扫一扫上面的微信公众号，订阅我的博客！

坚持原创技术分享，您的支持将鼓励我继续创作！