问题一：实现二叉树的先序、中序、后序遍历，包括递归方式和非递归方式
二叉树的遍历序列
对于遍历序列，把打印节点值放在第一次访问节点，就是先序遍历；放在第二次访问节点，就是中序遍历；放在第三次访问节点，就是后序遍历
递归时每个节点都是访问三次，关键是打印时机
递归方式
非递归方式先序遍历：准备一个栈，先压右边的再压左边的
非递归方式先序遍历
非递归方式中序遍历：当前节点为空，从栈弹出一个打印，弹出节点向右移动；若不为空压入栈，入栈节点向左移动
非递归方式中序遍历
非递归方式后序遍历：先，中序遍历只要做到访问一个节点两次，但后序要三次（参考递归方式），解决方法是用两个栈，一个按中右左存入，另一个接受前一个的弹出，最后形成左右中
非递归方式后序遍历
问题二：直观打印一颗二叉树（有空间感）
直观打印一颗二叉树
问题三：在二叉树中找到一个节点的后继节点
在二叉树中找到一个节点的后继节点
前驱节点：中序遍历中每个节点的前一个节点；后继节点：中序遍历中每个节点的后一个节点
解决思路：如果一个节点没有右节点，就找父节点并判断这个节点是否为父节点的左孩子，不是继续向上找，直到找到，返回此时的父节点；如果一个节点有右节点，就返回右节点子树上最左的一个
问题四：二叉树的序列化和反序列化
序列化：内存中的二叉树记录到文本中，可以先序中序后序，或者按层序列化
先序方式序列化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)
网友评论