代码随想录(Python)

从二叉树开始学习~

一、二叉树

（一）重点内容

        种类：解题过程中主要有满二叉树与完全二叉树、二叉搜索树

        二叉搜索树（BST：Binary search tree）：简单理解为左节点对应的值及其子树所有节点的值大于根节点的值大于右节点对应的值及其子树所有节点的值及其子树，注意子树为空的情况。

        平衡二叉树（AVL）：BST的基础上限制了任意节点的两个子树高度差的绝对值不超过1，性质可以为空树。

        二叉树存储方式：链式与顺序存储均可

        遍历方式：广度、深度优先遍历。进一步拓展为前序、中序、后序、层次遍历。

        python代码实现：

（二）二叉树的递归遍历(注释应该用双引号)

        1.递归三要素：

        确定参数和返回值、确定终止条件、确定单层递归的逻辑。

        2.递归实现：

        视情况而定，对于print操作进行修改。

        个人觉得递归操作用处没有迭代操作那么大，而且递归操作比较简单。

        3.迭代操作(栈与标记法同用)：

        之前不是很懂后序遍历的迭代法，代码随想录用一个统一的模板，给我整通透了。

        重点来了，例如对于前序遍历而言，是根左右，那我们只需要将根节点最后入栈，按照遍历的反顺序入栈，并在根节点入栈后插入一个None节点。然后遇到None节点就下一个元素出栈，然后添加到res列表中。这相比之前我看到的迭代算法来说，要简单不少，也便于记忆。具体实现如下：

        对于中序遍历，只要将根节点入栈的顺序放在左孩子节点入栈之前。

        对于后序遍历，只要将根节点入栈顺序放在右孩子节点入栈之前。

        4.层序遍历：

        层序遍历的递归代码不可能实现，因为使用队列作为遍历数据结构来实现的，一般都是迭代遍历的方法，具体代码比较容易理解：

        需要遍历完每一层的结点，用一个level去存放每一层的结点的val值。 

        具体题目：

        (1)二叉树的层序遍历：

                同模板