day15 | 层序遍历、 226.翻转二叉树、 101. 对称二叉树

链接

题目链接：

解题及思路学习

层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

随想录：借助一个队列实现。

102. 二叉树的层序遍历

/**
 * 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<vector<int>> levelOrder(TreeNode* root) {
        //定义一个queue
        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;
    }
};
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
37
38

107.二叉树的层次遍历 II

最后只需要将result的顺序改一下就行，但是注意，reverse是直接在result上操作的

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        //创建一个记录的容器
        vector<vector<int>> result;
        //创建一个队列
        queue<TreeNode*> que;
        //将根节点压入队列
        if (root != NULL) que.push(root);
        //构建循环层次遍历
        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);
        }
        reverse(result.begin(), result.end());
        return result;
    }
};
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

199. 二叉树的右视图

层次遍历，但是只保留每一层的最后一个节点

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        //创建保存结果的数组
        vector<int> result;
        //创建queue
        queue<TreeNode*> que;
        //处理头节点
        if (root != NULL) que.push(root);
        //创建循环
        while(!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++){
                TreeNode* node = que.front();
                que.pop();
                if (i == size -1) {
                    result.push_back(node->val);
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }   
        }
        return result;
    }
};
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

637. 二叉树的层平均值

每一层的数组计算一下其中的平均值，或者直接遍历的时候，加起来除以size

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        //queue
        queue<TreeNode*> que;
        //result
        vector<double> result;
        if (root != NULL) que.push(root);
        //circle
        while(!que.empty()) {
            int size = que.size();
            double sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                ave += node->val;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(sum/size);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

429. N 叉树的层序遍历

之前是二叉树，这个n叉数和前面的代码基本相同，但是要注意，在孩子节点时，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();
            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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

利用一个临时值记录每一行的最大值。

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();
            int max = que.front()->val;
            for ( int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                max = node->val > temp ? node-> val: max;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(temp);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

层次遍历，当遍历的时候，将next指针指向下一个节点，没有则赋值为NULL.

在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            // vector vec;
            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; // 本层前一个节点next指向本节点
                    nodePre = nodePre->next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            nodePre->next = NULL; // 本层最后一个节点指向NULL
        }
        return root;

    }
};
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

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

跟上一题不同之处在于不是完美二叉树了

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            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; // 本层前一个节点next指向本节点
                    nodePre = nodePre->next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            nodePre->next = NULL; // 本层最后一个节点指向NULL
        }
        return root;
    }
};
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

104. 二叉树的最大深度

层次遍历模板，每一层+1.

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

111. 二叉树的最小深度

层次遍历，当左右子节点都没有的时候，判断为最小深度

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

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

!https://assets.leetcode.com/uploads/2021/03/14/invert1-tree.jpg

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
1
2

思考：对于每个节点，都将左右子节点对调，即可完成整体反转。用while循环一直遍历，可以用栈也可以用队列来存储。（下面代码中，交换的步骤可以直接用swap()函数）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while(!st.empty())
        {
            TreeNode* temp;
            TreeNode* node = st.top();
            st.pop();
            temp = node->left;
            node->left = node->right;
            node->right = temp;
            if (node->left) st.push(node->left);
            if (node->right) st.push(node->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:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10

递归方法，确实代码很简洁。

递归三部曲：

确定递归函数的参数和返回值

2 确定终止条件

确定单层递归的逻辑

101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

!https://assets.leetcode.com/uploads/2021/02/19/symtree1.jpg

输入：root = [1,2,2,3,4,4,3]
输出：true
1
2

思考：这题可以考虑使用层次遍历法，判断每一层是否对称（如果对称，原序列等于reverse之后的序列）。

注：思路有问题，层次遍历的时候只能判断这一行的数值是否对称，不能判断位置是否对称

下面是错误代码：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        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);
            }
            vector<int> temp = vec;
            reverse(vec.begin(), vec.end());
            if (temp != vec) return false;
        }
        return true;
    }
};

修正：
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);
        que.push(root->right);
        while(!que.empty()) {
            TreeNode* leftNode = que.front();que.pop();
            TreeNode* rightNode = que.front();que.pop();
            if (!leftNode && !rightNode) continue;

            if ((!leftNode || !rightNode || leftNode->val != rightNode->val)) {
                return false;
            }
            que.push(leftNode->left);
            que.push(rightNode->right);
            que.push(leftNode->right);
            que.push(rightNode->left);
        }
        return true;        
    }
};
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
37
38
39
40
41
42
43
44
45
46
47
48

随想录：需要判断左右孩子信息，则要考虑后续的遍历方式。

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

        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        bool result = outside && inside;
        return result;
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        else {
            return compare(root->left, root->right);
        } 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

困难及收获

困难

层序遍历的思想倒是练的挺熟，遍历的方法不熟。

今日收获

遍历的思想，层序遍历思想。递归遍历的时候要注意前中后的顺序。

相关阅读:
《Linux运维篇：Linux系统运维指南》
OpenCV杂记（1）：绘制OSD（cv::getTextSize, cv::putText）
独立站运营中如何提升客户留存率？客户细分很重要！
ffmpeg转码视频
 Java 入门指南：使用 Docker 创建容器化 Spring Boot 应用程序
 网络安全系列-四十: suricata 的运行模型Running mode讲解
 MySQL数据文件被误删，如何进行恢复？
ImmunoChemistry艾美捷ELISA洗涤缓冲液说明书
 19.在springboot中集成dubbo（zookeeper）
python配置到系统环境中
原文地址：https://blog.csdn.net/weixin_45048521/article/details/131144836