二叉树专题讲解

指南

数据结构和算法学习指南

数据结构的存储方式只有两种：数组(顺序存储) 和 链表(链式存储)。其他的结构，如队列，栈，图等都是以这两种为基础演变的。

数据结构的基本操作：遍历 + 访问，具体一点就是：增删改查。数据结构类型有很多，但是他们的目的都是在不同的应用场景下，尽可能高效的增删改查，这就是数据结构的使命。

数组遍历是典型的线性迭代结构，链表便利兼具迭代和递归，二叉树则是典型的非线性递归。

数据结构是工具，算法则是通过合适的工具解决特定问题的方法。算法刷题建议从二叉树开始。二叉树最容易培养框架思维，大部分算法技巧，本质上都是树的遍历问题。

刷通二叉树第一期

前置的一些基本概念：深度遍历/广度遍历。深度遍历有前序，中序和后序三种遍历方式。广度便利及我们平时说的层次遍历。

前序遍历: 根结点 -> 左子树 -> 右子树

中序遍历: 左子树 -> 根结点 -> 右子树

后序遍历: 左子树 -> 右子树 -> 根结点

层次便利: 只需按层次遍历既可

PS: 吐槽一下前中后的定义，老是搞错，抓住根本，这些形容词都是用来表述根节点的。前序就是 root 先，左右子树的顺序都是固定的。

完美二叉树(Perfect Binary Tree)：也翻译为满二叉树，理解为正三角形就行

完全二叉树(Complete Binary Tree)：倒数第二层为完美二叉树，最后一层不全，叶子结点左对齐

完满二叉树(Full Binary Tree): 只要有孩子，就是两个

第一期

通过练习，熟悉树的遍历框架

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}