代码随想录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;}

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