代码随想录day12

144.二叉树的前序遍历

//明确递归的函数，结束边界，单层逻辑

void traversal(TreeNode* node, vector<int>& list){ if(node == nullptr){ return; } list.push_back(node->val); traversal(node->left, list); traversal(node->right, list); } vector<int> preorderTraversal(TreeNode* root) { vector<int> result; traversal(root, result); return result; }

//迭代法

vector<int> preorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> traversal; if(root == nullptr){ return result; } traversal.push(root); while(!traversal.empty()){ TreeNode* cur = traversal.top(); result.push_back(cur->val); traversal.pop(); if(cur->right) traversal.push(cur->right); if(cur->left) traversal.push(cur->left); } return result; }

//统一迭代法

vector<int> preorderTraversal(TreeNode* root) { vector<int> result; stack<pair<TreeNode*, bool>> st; if(root == nullptr) return result; st.push(make_pair(root, false)); while(!st.empty()){ auto node = st.top(); st.pop(); if(node.second){ result.push_back(node.first->val); } else { if(node.first->right) st.push(make_pair(node.first->right, false)); if(node.first->left) st.push(make_pair(node.first->left, false)); st.push(make_pair(node.first, true)); } } return result; }

145.二叉树的后序遍历

void traversal(TreeNode* node, vector<int>& list){ if(node == nullptr){ return; } traversal(node->left, list); traversal(node->right, list); list.push_back(node->val); } vector<int> postorderTraversal(TreeNode* root) { vector<int> result; traversal(root, result); return result; }

//迭代法 左右中-》中右左-〉中左右

vector<int> postorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> traversal; if(root == nullptr) return result; traversal.push(root); while(!traversal.empty()){ TreeNode* cur = traversal.top(); result.push_back(cur->val); traversal.pop(); if(cur->left) traversal.push(cur->left); if(cur->right) traversal.push(cur->right); } reverse(result.begin(), result.end()); return result; }

//统一迭代法

vector<int> postorderTraversal(TreeNode* root) { vector<int> result; stack<pair<TreeNode*,bool>> st; if(root == nullptr) return result; st.push(make_pair(root, false)); while(!st.empty()){ auto node = st.top(); st.pop(); if(node.second){ result.push_back(node.first->val); }else{ st.push(make_pair(node.first, true)); if(node.first->right) st.push(make_pair(node.first->right, false)); if(node.first->left) st.push(make_pair(node.first->left, false)); } } return result; }

94.二叉树的中序遍历

void traversal(TreeNode* node, vector<int>& list){ if(node == nullptr){ return; } traversal(node->left, list); list.push_back(node->val); traversal(node->right, list); } vector<int> inorderTraversal(TreeNode* root) { vector<int> result; traversal(root, result); return result; }

//迭代法，需理解左中右无法直接处理

vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; if(root == nullptr) return result; TreeNode* cur = root; while(cur != nullptr || !st.empty()){ if(cur != nullptr){ st.push(cur); cur = cur->left; }else{ cur = st.top(); result.push_back(cur->val); st.pop(); cur = cur->right; } } return result; }

//统一迭代法

vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<pair<TreeNode*, bool>> st; if(root == nullptr) return result; st.push(make_pair(root, false)); while(!st.empty()){ auto node = st.top(); st.pop(); if(node.second) { result.push_back(node.first->val); }else{ if(node.first->right) st.push(make_pair(node.first->right, false)); st.push(make_pair(node.first, true)); if(node.first->left) st.push(make_pair(node.first->left, false)); } } return result; }

102.二叉树的层序遍历

//广度优先遍历，使用queue的迭代法

vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; queue<TreeNode*> qe; if(root == nullptr) return result; qe.push(root); while(!qe.empty()){ int sz = qe.size(); vector<int> tmp; for(int i = 0; i < sz; i++){ auto node = qe.front(); qe.pop(); tmp.push_back(node->val); if(node->left) qe.push(node->left); if(node->right) qe.push(node->right); } result.push_back(tmp); } return result; }

//递归法

void order(vector<vector<int>>& result, TreeNode* node, int depth){ if(node == nullptr) return; if(result.size() == depth) result.push_back(vector<int>()); result[depth].push_back(node->val); if(node->left) order(result, node->left, depth+1); if(node->right) order(result, node->right, depth+1); return; } vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; order(result, root, 0); return result; }

107.二叉树的层序遍历II

上题结果reverse即可。

199.二叉树的右视图

//保存层序遍历中每层的最后一位

vector<int> rightSideView(TreeNode* root) { vector<int> result; queue<TreeNode*> qe; if(root == nullptr) return result; qe.push(root); while(!qe.empty()){ int sz = qe.size(); vector<int> tmp; for(int i = 0; i < sz; i++){ TreeNode* node = qe.front(); qe.pop(); tmp.push_back(node->val); if(node->left){ qe.push(node->left); } if(node->right) { qe.push(node->right); } } result.push_back(tmp[sz-1]); } return result; }

637.二叉树的层平均值

//计算每层的总和然后除以size即可

vector<double> averageOfLevels(TreeNode* root) { vector<double> result; queue<TreeNode*> qe; if(root == nullptr) return result; qe.push(root); while(!qe.empty()){ int sz = qe.size(); double tmp = 0; for(int i = 0; i < sz; i++){ TreeNode* node = qe.front(); qe.pop(); tmp += node->val; if(node->left) qe.push(node->left); if(node->right) qe.push(node->right); } double x = tmp/sz; result.push_back(x); } return result; }

429.N叉树的层序遍历

vector<vector<int>> levelOrder(Node* root) { vector<vector<int>> result; queue<Node*> qe; if(root == nullptr) return result; qe.push(root); while(!qe.empty()){ int sz = qe.size(); vector<int> tmp; for(int i = 0; i < sz; i++){ Node* nd = qe.front(); qe.pop(); tmp.push_back(nd->val); int cd_sz = nd->children.size(); for(int j = 0; j < cd_sz; j++){ if(nd->children[j]){ qe.push(nd->children[j]); } } } result.push_back(tmp); } return result; }

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

vector<int> largestValues(TreeNode* root) { vector<int> result; queue<TreeNode*> qe; if(root == nullptr) return result; qe.push(root); while(!qe.empty()){ int sz = qe.size(); int tmp = qe.front()->val; for(int i = 0; i < sz; i++){ TreeNode* node = qe.front(); qe.pop(); if(node->val > tmp) tmp = node->val; if(node->left) qe.push(node->left); if(node->right) qe.push(node->right); } result.push_back(tmp); } return result; }

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

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

Node* connect(Node* root) { queue<Node*> qe; if(root == nullptr) return root; qe.push(root); while(!qe.empty()){ int sz = qe.size(); for(int i = 0; i < sz; i++){ Node* nd = qe.front(); qe.pop(); if(i == sz - 1){ nd->next = nullptr; } else{ nd->next = qe.front(); } if(nd->left) qe.push(nd->left); if(nd->right) qe.push(nd->right); } } return root; }

104.二叉树的最大深度

int maxDepth(TreeNode* root) { int result = 0; queue<TreeNode*> qe; if(root == nullptr) return result; qe.push(root); while(!qe.empty()){ int sz = qe.size(); for(int i = 0; i < sz; i++){ TreeNode* nd = qe.front(); qe.pop(); if(nd->left) qe.push(nd->left); if(nd->right) qe.push(nd->right); } result += 1; } return result; }

111.二叉树的最小深度

int minDepth(TreeNode* root) { int result = 0; queue<TreeNode*> qe; if(root == nullptr) return result; qe.push(root); while(!qe.empty()){ int sz = qe.size(); result += 1; for(int i = 0; i < sz; i++){ TreeNode* nd = qe.front(); qe.pop(); if(!nd->left && !nd->right) return result; if(nd->left) qe.push(nd->left); if(nd->right) qe.push(nd->right); } } return result; }

最近几天有点事，拖了进度，后序需坚持跟上，加油