二叉树基础概念

结点：使用树结构储存的每一个数据结点都称为结点；
父结点，子结点，兄弟结点概念；
树根结点：
叶子结点：如果结点没有任何的子结点，就称为叶子结点；

图中 Z部分称为子树
单个结点也是子树

对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（Degree）。
一棵树的度是树内各结点的度的最大值。
一棵树的深度（高度）是树中结点所在的最大的层次。

二叉树：
1.二叉树中，第 i 层最多有 2i-1 个结点。
2.如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
3.二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

二叉树存储结构：包含数据，左右孩子结点的指针

迭代法：利用queue （BFS）

class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
// 这⾥⼀定要使⽤固定⼤⼩size，不要使⽤que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
};

二叉树层先算法