1，二叉树的层序遍历
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
来源：
剑指 Offer 32 – I. 从上到下打印二叉树
层次遍历需要借助
队列
实现，将每一层的节点入队列q，遍历队列的同时生成下一层的节点队列。（其他结构如vector，list也行，栈不推荐）。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
// 层次遍历
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
vector<int> level;
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* t = q.front(); q.pop();
level.push_back(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
result.push_back(level);
}
return result;
}
};给定一个二叉树，返回其节点值自底向上的层序遍历。
与上题相似，向result添加数据时，插入到开头即可。
剑指 Offer 32 – III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
与上题相似，输出result前，反转result中下标为奇数的数组。
输出每层的平均值，将数组变量level替换成double变量sum并累加，平均值=sum / size;
2，N叉树的层序遍历
给定一个 N 叉树，返回其节点值的
层序遍历
。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
来源：
429. N 叉树的层序遍历
与二叉树遍历相似，不同的是，节点的孩子不再是左右2个，可能1个可能多个。
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> result;
// 层次遍历
queue<Node*> q;
if (root) q.push(root);
while (!q.empty()) {
vector<int> level;
int size = q.size();
for (int i = 0; i < size; i++) {
Node* t = q.front(); q.pop();
level.push_back(t->val);
for (int j = 0; j < t->children.size(); j++) {
q.push(t->children[j]);
}
}
result.push_back(level);
}
return result;
}
};
3，二叉树的深度
从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
求解二叉树的深度可以使用层次遍历，返回层数即可。
来源：
剑指 Offer 55 – I. 二叉树的深度
&&
104. 二叉树的最大深度
class Solution {
public:
int maxDepth(TreeNode* root) {
int depth = 0;
// 层次遍历
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
depth++;
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* t = q.front(); q.pop();
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
return depth;
}
};
递归写法：
递归终止条件：节点为空返回深度0，节点为叶子节点返回1
递归调用条件：左子树深度 和 右子树深度比较，返回最大值+1。
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return left > right ? left + 1 : right + 1;
}
};
4，二叉树的最小深度
来源：
111. 二叉树的最小深度
与题3类似，层次遍历时，遇到叶节点退出。
class Solution {
public:
int minDepth(TreeNode* root) {
int depth = 0;
// 层次遍历
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
depth++;
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* t = q.front(); q.pop();
if (t->left == NULL && t->right == NULL) return depth;
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
return depth;
}
};
递归写法：
int minDepth(struct TreeNode* root){
if (root == NULL) return 0;
if (root->left == NULL) {
if (root->right == NULL) {
return 1;
} else {
return 1 + minDepth(root->right);
}
} else {
if (root->right == NULL) {
return 1 + minDepth(root->left);
} else {
int left = 1 + minDepth(root->left);
int right = 1 + minDepth(root->right);
return left < right ? left : right;
}
}
}
5，最深叶节点的和
来源：
1302. 层数最深叶子节点的和
与题1相似，每一层都计算和，返回最后一层的和。
class Solution {
public:
int deepestLeavesSum(TreeNode* root) {
int sum = 0;
// 层次遍历
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
sum = 0;
vector<int> level;
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* t = q.front(); q.pop();
sum += t->val;
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
return sum;
}
};
6，最深节点的最近公共祖先
来源：
1123. 最深叶节点的最近公共祖先
&&
865. 具有所有最深节点的最小子树
计算当前节点左子树和右子树的高度，如果左子树与右子树等高，则返回当前节点。如果左子树高于右子树，说明返回节点在左子树上，当前节点指向左子树；如果右子树高，当前节点指向右子树。如此反复判断直到找出最近公共祖先。
class Solution {
public:
TreeNode* lcaDeepestLeaves(TreeNode* root) {
TreeNode* p = root;
while (p != NULL) {
int left = depth(p->left);
int right = depth(p->right);
if (left == right) break;
if (left < right) {
p = p->right;
} else {
p = p->left;
}
}
return p;
}
int depth(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
int left = depth(root->left);
int right = depth(root->right);
return left > right ? left + 1 : right + 1;
}
};
7，元素和最大的层
来源：
1161. 最大层内元素和
原题描述不易读懂，简单说，比较每层元素的和，返回最大和所在的层。如果最大和存在于多个层，返回层号最小的。
累加每层元素后比较，因为元素可以是负数，所以max初始化为一个很小的负数。
class Solution {
public:
int maxLevelSum(TreeNode* root) {
int max = -999999999;
int depth = 0;
int result = 0;
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
int s = 0;
depth++;
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode* p = q.front(); q.pop();
s += p->val;
if (p->left) q.push(p->left);
if (p->right) q.push(p->right);
}
if (max < s) {
max = s;
result = depth;
}
}
return result;
}
};
8，平衡二叉树
平衡二叉树的定义：任意一个节点，其两棵子树的高度差不超过 1。
来源：
利用题3的maxDepth函数计算当前节点2棵子树的深度，如果深度差满足条件并且左右子树也是平衡二叉树，则返回true。
class Solution {
public:
bool isBalanced(TreeNode* root) {
//return height(root) >= 0;
if (root == NULL) return true;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
int d = left - right;
if (d > 1 || d < -1) return false;
return isBalanced(root->left) && isBalanced(root->right);
}
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return left > right ? left + 1 : right + 1;
}
};