鄂北局网站建设者风采,清远住房和城乡建设部网站,湖北省网站建设,搜索引擎优化分析报告Day15 层序遍历102.二叉树的层序遍历107.二叉树的层次遍历 II199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针II104.二叉树的最大深度111.二叉树的最小深度 226… Day15 层序遍历102.二叉树的层序遍历107.二叉树的层次遍历 II199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针II104.二叉树的最大深度111.二叉树的最小深度 226.翻转二叉树101.对称二叉树 层序遍历
层序遍历就相当于图论中的广度优先搜索。 递归遍历就相当于图论中的深度优先搜索。 只使用二叉树结构无法层序遍历。因为当你遍历到一个某个节点左节点时无法遍历到其右节点。需要一个其他结构来辅助。选择使用队列queue保存每一层待遍历的元素。
102.二叉树的层序遍历
题目链接:102.二叉树的层序遍历 迭代
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* que;//记录每层节点vectorvectorint res;if (root) que.push(root);while (!que.empty()) {vectorint 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, vectorvectorint res, int depth) {if (!cur) return;//返回条件if (res.size() depth) res.push_back(vectorint());//开辟一个空的vectorint
// if (res.size() depth) res.emplace_back();等价于上一行res[depth].push_back(cur-val);recursive(cur-left, res, depth 1);//depth1是回溯recursive(cur-right, res, depth 1);//depth1是回溯}vectorvectorint levelOrder(TreeNode* root) {vectorvectorint res;int depth 0;//给res二维数组用来赋外层索引recursive(root, res, depth);return res;}
};107.二叉树的层次遍历 II
题目链接:107.二叉树的层次遍历 II 因为节点遍历只能从根节点开始。所以就正常层序遍历最后结果反转一下。 迭代
class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {vectorvectorint res;queueTreeNode* que;if (root) que.push(root);while (!que.empty()) {int size que.size();vectorint 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, vectorvectorint 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);//depth1是回溯recursion(root-right, res, depth 1);//depth1是回溯}vectorvectorint levelOrderBottom(TreeNode* root) {vectorvectorint res;int depth 0;recursion(root, res, depth);reverse(res.begin(), res.end());return res;}
};199.二叉树的右视图
题目链接199.二叉树的右视图 迭代
class Solution {
public:vectorint rightSideView(TreeNode* root) {queueTreeNode* que;vectorint 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, vectorint res, int depth) {if (!root) return;if (res.size() depth) res.emplace_back(root-val);//先加入右节点元素因为是保存右节点recursion(root-right, res, depth 1);//depth1是回溯recursion(root-left, res, depth 1);//depth1是回溯}vectorint rightSideView(TreeNode* root) {vectorint res;int depth 0;recursion(root, res, depth);return res;}
};637.二叉树的层平均值
题目链接:637.二叉树的层平均值
class Solution {
public:vectordouble averageOfLevels(TreeNode* root) {vectordouble res;queueTreeNode* 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:vectorvectorint levelOrder(Node* root) {queueNode* que;vectorvectorint res;if (root) que.push(root);while (!que.empty()) {int size que.size();vectorint 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:vectorint largestValues(TreeNode* root) {vectorint res;queueTreeNode* 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) {queueNode* 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) {queueNode* 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) {queueTreeNode* 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) {queueTreeNode* 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) {stackTreeNode* 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) {stackTreeNode* 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) {stackTreeNode* 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) {queueTreeNode* 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;stackTreeNode* 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;}
};
