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;
}最近几天有点事，拖了进度，后序需坚持跟上，加油