代码随想录Day15

 · 2024-1-9 · 次阅读

二叉树层序遍历

102 二叉树的层序遍历

思路

队列来实现每一层的存储和计数 每次出队的元素通过size控制，都是父节点的个数，然后再从父节点去访问底下的子节点最后实现子节点层序存储到vec里面，再把vec放到二维vec里

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if(root!=NULL) que.push(root);
        vector<vector<int>> result;
        while(!que.empty()){
            int size =que.size();
            vector<int> vec;
            for(int i=0;i<size;i++){
                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. 二叉树的层序遍历 II

思路

层序遍历之后翻转一下即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> result;
        if(root!=NULL){
            que.push(root);
        }
        while(!que.empty()){
            int size =que.size();
            TreeNode* cur=que.front();
            vector<int> vec;
            while(size--){
                cur=que.front();
                vec.push_back(cur->val);
                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            result.push_back(vec);
        }
        reverse(result.begin(),result.end());
        return result;
        }
};

199. 二叉树的右视图

思路

层序遍历，当队列的最后一个元素在处理时加入 结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> result;
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            int size =que.size();
            TreeNode* cur;
            
            while(size--){
                cur=que.front();
                que.pop();
                if(size==0) result.push_back(cur->val);
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return result;
    }
};

637 二叉树的层平均值

处理平均值的精度时要保证所有的数据类型一致

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
public:
double calculateAverage(const std::vector<double>& v) {
    if (v.empty()) return 0.0; // 防止除以0

    // 使用 std::accumulate 来求和
    double sum = std::accumulate(v.begin(), v.end(), 0.0);
    
    // 计算平均值
    return static_cast<double>(sum) / v.size();
} 
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> que;
        vector<double> result;
        double sum;
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            TreeNode * cur;
            vector<double> vec;
            int size = que.size();
            int q_size=size;
            while(size--){
                cur=que.front();
                vec.push_back(cur->val);
                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
                
            }
            sum =calculateAverage(vec);
            result.push_back(sum);
        }
        return result;
    }
};

429. N 叉树的层序遍历

思路

遍历次数增多一个循环访问节点 访问一下所有的children节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;
        if(root!=NULL) que.push(root);
        vector<vector<int>> result;
        while(!que.empty()){
            int size=que.size();
            vector<int> vec;
            for(int i=0;i<size;i++){
                Node * node =que.front();
                que.pop();
                vec.push_back(node->val);
                for(int i=0;i<node->children.size();i++){
                    if(node->children[i])que.push(node ->children[i]);
                }
            }
            result.push_back(vec);
        }
        return result;
    }
};

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

思路

正常进行层序遍历，每次提前保存上一个节点的位置直到size-1的位置就不保存了。

  • 错误记录： 每一层的最后一个节点处理有问题，最后一个节点访问了空的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        vector <Node *> vec;
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            int size =que.size();
            while(size --){
                Node * cur;
                cur =que.front();
                que.pop();
                if(!que.empty()){cur->next=que.front();}
				if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return root;
    }
};
  • 正确 -直接用计数器解决即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        vector <Node *> vec;
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            int size =que.size();
            for(int i=0;i<size;i++){
                Node * cur;
                cur =que.front();
                que.pop();
               if(i<size-1){cur->next=que.front();}
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return root;
    }
};

104. 二叉树的最大深度

思路

层序遍历模板题，全部的层用队列刷一遍计数器计算即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if(root ==NULL) return 0;
        int dep =0;
        que.push(root);
        while(!que.empty()){
            TreeNode* cur=root;
            int size =que.size();
            dep++;
            while(size--){
                cur=que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return dep;
    }
};

111. 二叉树的最小深度

思路

层序遍历二叉树，第一个遇到的没有左右孩子的节点即为最浅层的节点返回深度即可

在104基础上加一行代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minDepth(TreeNode* root) {
queue<TreeNode*> que;
        if(root ==NULL) return 0;
        int dep =0;
        que.push(root);
        while(!que.empty()){
            TreeNode* cur=root;
            int size =que.size();
            dep++;
            while(size--){
                cur=que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                if(cur->left==NULL&&cur->right==NULL) return dep;
            }
        }
        return dep;

    }
};

层序遍历小总结

美滋滋 刷的很爽

翻转二叉树

经典题目

层序 ，先序，后序，都可以实现

先用层序做一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode *> que;
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            TreeNode * cur;

            int size =que.size();
            while(size--){
                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;
    }
};
  • 前序递归
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* reverse(TreeNode * root){
        if(root==NULL)    return root;
        swap(root->left, root->right);
        reverse(root->left);
        reverse(root->right);
        return root;
    }
    TreeNode* invertTree(TreeNode* root) {
        return reverse(root);
    }
};

对称二叉树的判定

思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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);
    }
};
赏