左神初级算法课程第五讲笔记-二叉树

问题一：实现二叉树的先序、中序、后序遍历，包括递归方式和非递归方式

二叉树的遍历序列

对于遍历序列，把打印节点值放在第一次访问节点，就是先序遍历；放在第二次访问节点，就是中序遍历；放在第三次访问节点，就是后序遍历

递归时每个节点都是访问三次，关键是打印时机

递归方式

非递归方式先序遍历：准备一个栈，先压右边的再压左边的

非递归方式先序遍历

非递归方式中序遍历：当前节点为空，从栈弹出一个打印，弹出节点向右移动；若不为空压入栈，入栈节点向左移动

非递归方式中序遍历

非递归方式后序遍历：先，中序遍历只要做到访问一个节点两次，但后序要三次（参考递归方式），解决方法是用两个栈，一个按中右左存入，另一个接受前一个的弹出，最后形成左右中

非递归方式后序遍历

问题二：直观打印一颗二叉树（有空间感）

直观打印一颗二叉树

问题三：在二叉树中找到一个节点的后继节点

在二叉树中找到一个节点的后继节点

前驱节点：中序遍历中每个节点的前一个节点；后继节点：中序遍历中每个节点的后一个节点

解决思路：如果一个节点没有右节点，就找父节点并判断这个节点是否为父节点的左孩子，不是继续向上找，直到找到，返回此时的父节点；如果一个节点有右节点，就返回右节点子树上最左的一个

问题四：二叉树的序列化和反序列化

序列化：内存中的二叉树记录到文本中，可以先序中序后序，或者按层序列化

先序方式序列化string:1_2_4_#_#_5_#_#_3_6_#_#_7_#_#_(#表示空节点)

先序方式序列化

反序列化：按序列化反向生成二叉树

问题五：这里视频卡了没看到

问题六：判断一颗二叉树是否平衡二叉树，这个问题统属于树形dp，即二叉树上的动态规划

平衡二叉树：一棵树任何一个节点，左子树与右子树高度差不超过1

按照递归思路：①先看左数是否平衡，不平衡就返回结果，平衡记录左数高度；②再看右数是否平衡，不平衡就返回结果，平衡记录右数高度，设计递归函数时子树判断返回结果应该包括（这棵树是否平衡和子树高度）

递归思路

问题七：判断一颗二叉树是否搜索二叉树、完全二叉树

搜索二叉树：一棵树上任何一个节点，左子树节点都比它小，右子树节点都比它大，即中序遍历升序排列，通常节点是不重复的

完全二叉树：二叉树按层遍历①一个节点有右节点没有左节点，返回false②一个节点不是左右节点均存在（两种情况，有左没右或者都没有），它后面遇到的节点都必须是叶节点

tip：用二叉树实现堆没有扩容代价（例如vector容量不够空间翻倍），二叉树只是一个节点一个节点的加

问题八：一颗完全二叉树求节点个数，要求时间复杂度低于O(N)

对于满二叉树高度为l，节点个数为2^l-1，①先找到一个节点的左边界（O(logN)），这样可以计算出左边界的高度，然后遍历右子树的左边界，观察右子树的左边界是否到了相同层数，到了那么整个左子树都是满的；计算2^层数=左子树加这个节点的数目，然后对这个节点的右子树按上述方式递归

②如果右子树的左边界没有到相同层数，那么暗示右子树是满的，计算2^（层数-1）=右子树加这个节点的数目，然后对左子树继续递归

这样每一层都只找一个节点，复杂度为O(logN)，找右子树左边界也是O(logN)，最终时间复杂度为O(logN)*O(logN)