二叉树相关算法
二叉树相关性质：
性质一：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
性质二：深度为k的二叉树至多有2^(k-1)个结点(k>=1)
性质三：对任意一颗二叉树T，若终端结点数为n0,而其度数为2的结点数为n2，则n0=n2+1.
性质四：具有n个结点的完全二叉树的深度为 ⌊log n⌋+1(以2为底)
满二叉树：深度为k，且有2^(k-1)个结点的二叉树。 在满二叉树中，每层结点都是满的，即每层节点都具有最大结点数。
完全二叉树：深度为k，结点数为n的二叉树，如果其结点1n的位置序号分别于满二叉树的节点1n的位置序号一一对应，则为完全二叉树。可见，满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。
题目
不分行从上往下打印二叉树
典型题例：
从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。
示例 ：
输入： 输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null] 8 / \ 12 2 / 6 / 4 输出：[8, 12, 2, 6, 4]
思路
(BFS)O(n)
我们从根节点开始按宽度优先的顺序遍历整棵树，每次先扩展左儿子，再扩展右儿子。
这样我们会：
- 先扩展根节点；
- 再依次扩展根节点的左右儿子，也就是从左到右扩展第二层节点；
- 再依次从左到右扩展第三层节点；
- 依次类推
所以BFS的顺序就是这道题目要求的顺序。
时间复杂度:
BFS时每个节点仅被遍历一次，所以时间复杂度是 O(n)O(n)。
代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> printFromTopToBottom(TreeNode* root) { vector<int> res; //定义返回数组 if (!root) return res; //判定边界条件 queue<TreeNode*> q; //定义队列 q.push(root); //把根结点加入队列 while (q.size()){ auto t = q.front(); q.pop(); res.push_back(t->val); //将val加入数组中 //判断是否有左右子树 if (t->left) q.push(t->left); //有左子树就加入队列 if (t->right) q.push(t->right); //有右子树就加入队列 } return res; } };
分行从上往下打印二叉树
典型题例：
从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。
示例 ：
输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null] 8 / \ 12 2 / 6 / 4 输出：[[8], [12, 2], [6], [4]]
思路
核心：
在上一道题 《不分行从上往下打印二叉树》 的基础上修改代码。
区别在于，每一层结束的时候，往queue里塞一个NULL做标记。
在queue里读取一个数出来之后，先看看是不是level标识符NULL(因为是BFS，当前level读完，下一个level有哪些要读的也都放在queue里了，可以在queue结尾给加一个新的NULL), 是的话再看看是不是整个树读完了(即queue里没有点了)。
时间复杂度分析：每个点遍历一次
代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> printFromTopToBottom(TreeNode* root) { vector<vector<int>> res; if(!root) return res; queue<TreeNode*> q; q.push(root); q.push(NULL); //root层的标识符 vector<int> cur; while(q.size()){ TreeNode* t = q.front(); q.pop(); if(t){ //跟上一道题同样的操作 cur.push_back(t->val); if(t->left) q.push(t->left); if(t->right) q.push(t->right); } else{ if(q.size()) q.push(NULL); res.push_back(cur); cur.clear(); } } return res; } };
充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
