算法Day15 | 层序遍历，102，107，199，637，429，515，116，117，104，111，226，101

层序遍历

层序遍历就相当于图论中的广度优先搜索。
递归遍历就相当于图论中的深度优先搜索。
只使用二叉树结构，无法层序遍历。因为当你遍历到一个某个节点左节点时，无法遍历到其右节点。需要一个其他结构来辅助。选择使用队列queue保存每一层待遍历的元素。

102.二叉树的层序遍历

题目链接:102.二叉树的层序遍历
迭代

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;//记录每层节点vector<vector<int>> res;if (root) que.push(root);while (!que.empty()) {vector<int> res1;int size = que.size();//用于记录弹出节点个数，就是每层节点个数while (size--) {TreeNode* cur = que.front();que.pop();res1.push_back(cur->val);//记录节点数值if (cur->left) que.push(cur->left);//左节点入队列if (cur->right) que.push(cur->right);//右节点入队列}res.push_back(res1);}return res;}
};

递归

class Solution {
public:void recursive(TreeNode* cur, vector<vector<int>>& res, int depth) {if (!cur) return;//返回条件if (res.size() == depth) res.push_back(vector<int>());//开辟一个空的vector<int>
//        if (res.size() == depth) res.emplace_back();等价于上一行res[depth].push_back(cur->val);recursive(cur->left, res, depth + 1);//depth+1是回溯recursive(cur->right, res, depth + 1);//depth+1是回溯}vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;int depth = 0;//给res二维数组，用来赋外层索引recursive(root, res, depth);return res;}
};

107.二叉树的层次遍历 II

题目链接:107.二叉树的层次遍历 II
因为节点遍历只能从根节点开始。所以就正常层序遍历，最后结果反转一下。
迭代

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> res;queue<TreeNode*> que;if (root) que.push(root);while (!que.empty()) {int size = que.size();vector<int> res1;while (size--) {TreeNode* cur = que.front();que.pop();res1.push_back(cur->val);if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}res.push_back(res1);}reverse(res.begin(), res.end());return res;}
};

递归

class Solution {
public:void recursion(TreeNode* root, vector<vector<int>>& res, int depth) {if (!root) return;if (res.size() == depth) res.emplace_back();res[depth].emplace_back(root->val);recursion(root->left, res, depth + 1);//depth+1是回溯recursion(root->right, res, depth + 1);//depth+1是回溯}vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> res;int depth = 0;recursion(root, res, depth);reverse(res.begin(), res.end());return res;}
};

199.二叉树的右视图

题目链接：199.二叉树的右视图
迭代

class Solution {
public:vector<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;vector<int> res;if (root) que.push(root);while (!que.empty()) {int size = que.size();while (size--) {TreeNode* cur = que.front();que.pop();if (!size)/*size = 0*/ res.push_back(cur->val);if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return res;}
};

递归

class Solution {
public:void recursion(TreeNode* root, vector<int>& res, int depth) {if (!root) return;if (res.size() == depth) res.emplace_back(root->val);//先加入右节点元素，因为是保存右节点recursion(root->right, res, depth + 1);//depth+1是回溯recursion(root->left, res, depth + 1);//depth+1是回溯}vector<int> rightSideView(TreeNode* root) {vector<int> res;int depth = 0;recursion(root, res, depth);return res;}
};

637.二叉树的层平均值

题目链接:637.二叉树的层平均值

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {vector<double> res;queue<TreeNode*> que;if (root) que.push(root);while (!que.empty()) {int size = que.size();double sum = 0;int cnt = 0;while (size--) {TreeNode* cur = que.front();que.pop();sum += cur->val;++cnt;if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}res.push_back(sum / cnt);}return res;}
};

429.N叉树的层序遍历

题目链接:429.N叉树的层序遍历

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {queue<Node*> que;vector<vector<int>> res;if (root) que.push(root);while (!que.empty()) {int size = que.size();vector<int> res1;while (size--) {Node* cur = que.front();que.pop();res1.push_back(cur->val);for (auto& i : cur->children) {que.push(i);}}res.push_back(res1);}return res;}
};

515.在每个树行中找最大值

题目链接：515.在每个树行中找最大值

class Solution {
public:vector<int> largestValues(TreeNode* root) {vector<int> res;queue<TreeNode*> que;if (root) que.push(root);while (!que.empty()) {int size = que.size();int maxValue = INT_MIN;while (size--) {TreeNode* cur = que.front();que.pop();maxValue = max(maxValue, cur->val);if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}res.push_back(maxValue);}return res;}
};

116.填充每个节点的下一个右侧节点指针

题目链接：116.填充每个节点的下一个右侧节点指针

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if (root) que.push(root);while (!que.empty()) {int size = que.size();while (size--) {Node* cur = que.front();que.pop();if (size) cur->next = que.front();//如果不是最后一个，与下一个节点相连if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return root;}
};

117.填充每个节点的下一个右侧节点指针II

题目链接：117.填充每个节点的下一个右侧节点指针II
与上一道题一模一样

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if (root) que.push(root);while (!que.empty()) {int size = que.size();while (size--) {Node* cur = que.front();que.pop();if (size) cur->next = que.front();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return root;}
};

104.二叉树的最大深度

题目链接：104.二叉树的最大深度

class Solution {
public:int maxDepth(TreeNode* root) {queue<TreeNode*> que;if (root) que.push(root);int res = 0;while (!que.empty()) {int size = que.size();while (size--) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}++res;}return res;}
};

111.二叉树的最小深度

题目链接:111.二叉树的最小深度

class Solution {
public:int minDepth(TreeNode* root) {queue<TreeNode*> que;if (!root) return 0;if (root) que.push(root);int res = 1;//至少有一层while (!que.empty()) {int size = que.size();while (size--) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);if (!cur->left && !cur->right) return res;}++res;}return res;}
};

---

226.翻转二叉树

题目链接：226.翻转二叉树
前、后序遍历很简单。
前序递归

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (!root) return nullptr;swap(root->left, root->right);//中invertTree(root->left);//左invertTree(root->right);//右return root;}
};

后序递归

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (!root) return nullptr;invertTree(root->left);//左invertTree(root->right);//右swap(root->left, root->right);//中return root;}
};

中序递归：代码上看是两次root->left

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (!root) return nullptr;invertTree(root->left);//左swap(root->left, root->right);//中//因为上一行代码已经处理过左树，处理完换成右树//接下来要处理的是原来的右树，但是已经变成左树了invertTree(root->left);//右return root;}
};

前序迭代

class Solution {
public:TreeNode* invertTree(TreeNode* root) {stack<TreeNode*> st;if (root) st.push(root);while (!st.empty()) {TreeNode* cur = st.top();if (cur) {st.pop();if (cur->right) st.push(cur->right);//右if (cur->left) st.push(cur->left);//左st.push(cur);//中st.push(nullptr);} else {st.pop();cur = st.top();st.pop();swap(cur->left, cur->right);}}return root;}
};

中序迭代

class Solution {
public:TreeNode* invertTree(TreeNode* root) {stack<TreeNode*> st;if (root) st.push(root);while (!st.empty()) {TreeNode* cur = st.top();st.pop();if (cur) {if (cur->right) st.push(cur->right);//右st.push(cur);//中st.push(nullptr);if (cur->left) st.push(cur->left);//左} else {cur = st.top();st.pop();swap(cur->left, cur->right);}}return root;}
};

后序迭代

class Solution {
public:TreeNode* invertTree(TreeNode* root) {stack<TreeNode*> st;if (root) st.push(root);while (!st.empty()) {TreeNode* cur = st.top();st.pop();if (cur) {st.push(cur);st.push(nullptr);if (cur->right) st.push(cur->right);if (cur->left) st.push(cur->left);} else {cur = st.top();st.pop();swap(cur->left, cur->right);}}return root;}
};

层序迭代

class Solution {
public:TreeNode* invertTree(TreeNode* root) {queue<TreeNode*> que;if (root) que.push(root);while (!que.empty()) {int size = que.size();while (size--) {TreeNode* cur = que.front();que.pop();swap(cur->left, cur->right);if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return root;}
};

---

101.对称二叉树

题目链接：101.对称二叉树
因为是先判断左右是否对称，再将结果传给中。顺序为左右中。所以是后序遍历。
递归

class Solution {
public:bool recursion(TreeNode* cur1, TreeNode* cur2) {//先排除空节点//这两个语句不能调换if (!cur1 && !cur2) return true;//非空之后，再排除值。if (!cur1 || !cur2 || cur1->val != cur2->val/*值判断一定要在非空之后*/) return false;auto outside = recursion(cur1->left, cur2->right);auto inside = recursion(cur1->right, cur2->left);return outside && inside;}bool isSymmetric(TreeNode* root) {if (!root) return true;return recursion(root->left, root->right);}
};

对于判断条件需要强调：

if (!cur1 && !cur2) return true;
if (!cur1 || !cur2) return false;

第一个if判断了同时为空的条件，满足条件，执行return。如果执行到第二条if语句，表示第一个if一定失效，即cur1和cur2不可能同时为空（有cur1为空，则cur2不为空；cur1不为空，则cur2为空），所以第二个if只需要判断cur1不为空（cur2一定为空）或者cur2不为空（cur1一定为空）即可。重要的是这两条if不能颠倒顺序。

if (!cur1 && !cur2) return true;
if (!cur1 && cur2) return false;
if (cur1 && !cur2) return false;

也就是，上面三条if可以用两条if来代替。因为第二条的if中的cur2和第三条if中的cur1一定是非空的，是多余的。

由于if后是return语句，所以可以不写else，先if( && )再写if( || )。更具一般性地，if( && ) else if ( || )。

迭代

class Solution {
public:bool isSymmetric(TreeNode* root) {if (!root) return true;stack<TreeNode*> st;st.push(root->left);st.push(root->right);while (!st.empty()) {auto leftNode = st.top();st.pop();auto rightNode = st.top();st.pop();if (!leftNode && !rightNode) continue;if (!leftNode || !rightNode || leftNode->val != rightNode->val)return false;st.push(leftNode->left);st.push(rightNode->right);st.push(leftNode->right);st.push(rightNode->left);}return true;}
};