代码随想录算法训练营day15 | ● 层序遍历 10 ● 226.翻转二叉树 ● 101.对称二叉树 2

层序遍历

102.二叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if(root != NULL)    que.push(root);
        while(!que.empty()){
            int size = que.size();  //对当前que.size()做一个快照
            vector<int> vec;
            while(size--){  //别用que.size(), 因为 que.size()在实时动态变化
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

107.二叉树的层序遍历 Ⅱ

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
    //正常走一遍层序遍历然后reverse一下
    vector<vector<int>> result;
    queue<TreeNode*> que;
    //que.push(root);
    if(root != NULL) que.push(root);
    while(!que.empty()){
        int size = que.size();
        vector<int> vec;
        while(size--){
            TreeNode *node = que.front();
            que.pop();
            vec.push_back(node->val);
            if(node->left) que.push(node->left);
            if(node->right) que.push(node->right);
        }
        result.push_back(vec);
    }
    reverse(result.begin(), result.end());
    return result;
    }
};

What if we replace the if(root != NULL) que.push(root); with just que.push(root); ?

Then, when the root is NULL, this line vec.push_back(node->val); will throw an error:

runtime error: member access within null pointer of type 'TreeNode' (solution.cpp)

Now, let's debug:

I've written these codes in vscode as you can see below:

#include<iostream>
#include<queue>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;  
    TreeNode() : val(0), left(NULL), right(NULL){}
};

int main(){
    queue<TreeNode*> que;
    cout << "before, the que's size is:" << que.size() << endl;
    que.push(NULL);
    cout << "after, the que's size is:" << que.size() << endl;
}

and run it, I got:

[Running] cd "d:\Operating System\" && g++ queue.cpp -o queue && "d:\Operating System\"queue
before, the que's size is:0
after, the que's size is:1

[Done] exited with code=0 in 1.802 seconds

absolutely, the NULL pointer will also be counted as 1 element in queue.

That's why we need to add an if sentence if(root != NULL) before que.push(root);

199.二叉树的右视图

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

note that my original code is:

		while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(node->val);	
        }

then I would get the next error:

this is the error: 不注意变量作用域。

花括号 { } 表示代码块，在其中定义的变量只在其中有效

See the debug code:

#include<iostream>
using namespace std;
int main(){
    int size = 3;
    while(size--){
        int x = 0;
    }
    cout << x << endl;
}

then I got an error:

loop.cpp:8:13: error: 'x' was not declared in this scope

cout << x << endl;

So is the same with result.push_back(node->val);

647.二叉树的层平均值

class Solution {
public:
    double sum(vector<double> vec){
        double sum = 0;
        for (double i : vec){
            sum += i; 
        }
        return sum;
    }

    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        queue<TreeNode*> que;
        if(root != NULL)    que.push(root);
        while(!que.empty()){
            double size = que.size();  //对当前que.size()做一个快照
            vector<double> vec;
            while(size--){  //别用que.size(), 因为 que.size()在实时动态变化
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(sum(vec) / vec.size());
        }
        return result;
    }
};

note, 强制类型转换

#include<iostream>
using namespace std;
int main(){
    
    int a = 9;
    int b = 2;
    cout << "a/b = " << a/b << endl;
    cout << "(double) a/b = "<< (double) a/b << endl;

    double c = 9;
    int d = 2;
    cout << "c/d = " << c/d << endl;
}

got

[Running] cd "d:\Operating System\" && g++ typetransfomer.cpp -o typetransfomer && "d:\Operating System\"typetransfomer
a/b = 4
(double) a/b = 4.5
c/d = 4.5

429.N叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        queue<Node*> que;
        if(root != NULL)    que.push(root);
        while(!que.empty()){
            int size = que.size();  //对当前que.size()做一个快照
            vector<int> vec;
            while(size--){  //别用que.size(), 因为 que.size()在实时动态变化
                Node* node = que.front();
                que.pop();
                vec.push_back(node->val);
                for(Node* cur : node->children)
                    if(cur)
                        que.push(cur);
            }
            result.push_back(vec);
        }
        return result;
    }
};

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> que;
        if(root != NULL)    que.push(root);
        while(!que.empty()){
            int size = que.size();  //对当前que.size()做一个快照
            int maxValue = INT_MIN;
            while(size--){  //别用que.size(), 因为 que.size()在实时动态变化
                TreeNode* node = que.front();
                que.pop();
                maxValue = node->val > maxValue ? node->val : maxValue;
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(maxValue);
        }
        return result;
    }
};

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

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root != NULL)    que.push(root);
        while(!que.empty()){
            int size = que.size();  //对当前que.size()做一个快照
            Node* nodePre;
            Node* node;
            for(int i = 0; i < size; i++){  //别用que.size(), 因为 que.size()在实时动态变化
                if(i == 0){
                    nodePre = que.front();
                    que.pop();
                    node = nodePre;
                }else{
                    node = que.front();
                    que.pop();
                    nodePre->next = node;   //本层前一个节点next指向结点
                    nodePre = nodePre->next;
                }
                if(node->left != NULL)  que.push(node->left);
                if(node->right != NULL) que.push(node->right);
            }
            nodePre->next = NULL;
        }
        return root; 
    }
};

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

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*>  que;
        if(root != NULL)    que.push(root);
        while(!que.empty()){
            int size = que.size();
            Node* nodePre;
            Node* node;
            for(int i = 0; i < size; i++){
                if(i == 0){
                    nodePre = que.front();
                    que.pop();
                    node = nodePre;
                }
                else{
                    node = que.front();
                    que.pop();
                    nodePre->next = node;
                    nodePre = nodePre->next;
                }
                if(node->left != NULL)  que.push(node->left);
                if(node->right != NULL) que.push(node->right);
            }
        nodePre->next = NULL;
        }
        return root;
    }
};

104.二叉树的最大深度

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

111.二叉树的最小深度

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

226. 翻转二叉树

mydemo--（层序遍历）

class Solution {
public:
    void swap(TreeNode* node1, TreeNode* node2){
        TreeNode* tmp = node1;
        node1 = node2;
        node2 = tmp;
    }

    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != NULL)    que.push(root);
        while(!que.empty()){
            TreeNode* Node = que.front();
            que.pop();
            //swap(Node->left, Node->right);    //这个函数没有用，why？
            TreeNode* tmp = Node->left;
            Node->left = Node->right;
            Node->right = tmp;
            if(Node->left != NULL)  que.push(Node->left);
            if(Node->right != NULL) que.push(Node->right);            
        }
        return root;
    }
};

卡哥demo--（深度遍历）

递归法我还是看不懂啊

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

101.对称二叉树

class Solution {
public:

    bool compare(TreeNode* left, TreeNode* right){
        if(left == NULL && right != NULL)   return false;
        else if(left != NULL && right == NULL)  return false;
        else if(left == NULL && right == NULL)  return true;
        else if(left->val != right->val)    return false;

        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        bool isSame = outside && inside;
        return isSame;
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)    return true;
        return compare(root->left, root->right);
    }
};

本栏目推荐文章
• 2024/1/13 算法笔记
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• 用jacoco统计JAVA项目测试代码覆盖率
• 算法练习题
• 算法学习Day26组合总和、分割回文串
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• 【SPFA】最短路的一种算法
• GDB调试之源代码查看与管理(六)

随想录 训练营 随想 算法 代码随想录 训练营 随想 算法 算法 随想录 训练营 随想 算法 随想录 训练营 序列 算法 随想录 训练营 数组 算法 随想录 训练营 总和 子集 算法 随想录 训练营 算法 解数 随想录 训练营 算法 随想录 训练营 九天 训练营 随想 代码python 算法 随想录 队列 训练营