“从0开始做LeetCode”之二叉树常见题目

 

1.实现二叉树的先序、中序、后序遍历，包括递归方式和非递归方式

递归
打印时机——>先序，中序，后序

非递归

先序

中序

后序

两个栈：
中左右——>中右左——>左右中

2.直观打印一棵树（用处不大）

3.找后继节点或者前驱

中序：左中右
后继节点，前驱节点

后继：

• 如果有右子树，则为右子树最左的节点
• 如果没有右子树，则往上找，父节点的左孩子是他就停

前驱：

• 如果有左子树，则为左子树最右的节点
• 如果没有左子树，则往上找，父节点的右孩子是他就停

4.介绍二叉树的序列化和反序列化

按先序、中序、后序

按层序列化

5.判断一颗二叉树是否是平衡二叉树

平衡二叉树：左子树和右子树高度差最多相差一

套路：递归函数很好用
收集左子树的信息，再收集右子树的信息

5.判断一颗数是否是搜索二叉树、判断一棵树是否是完全二叉树

搜索二叉树

左子树都比他小，右子树都比他大 即搜索二叉树

二叉树中序遍历，是依次升序的 即搜索二叉树

在非递归中序遍历里面改就行了

完全二叉树

按层遍历

1. 有右孩子，没有左孩子，不是完全二叉树
2. 有左没右，后面遇到的所有节点必须都是叶节点，否则不是完全二叉树

7.已知一颗完全二叉树，求其节点的个数

时间复杂度：O((log N)^2)