小丑西瓜9

这个屌丝很懒，什么也没留下！

热门标签

Day 15 层序遍历 226.翻转二叉树 101.对称二叉树

作者：小丑西瓜9 | 2024-04-08 17:13:51

踩

层序遍历

昨天讲的无论是递归还是迭代，都是深度优先遍历；

层序遍历则是广度优先遍历，一层一层的从左至右依次遍历，如图：

正如需要用栈这具有先进后出的数据结构来辅助进行深度优先遍历，同样需要另一种辅助数据结构来实现广度优先遍历；由于遍历的顺序是一层一层的从左至右，符合此条件的则是队列的先进先出；用队列实现方式则如下图所示：

下面这题可以说是母题一般的存在

力扣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<TreeNode*> que;//定义队列来存放二叉树节点
        vector<vector<int>> res;//定义二维数组来存放每一层的节点
        if(root != NULL)	que.push(root);
        else return res;
        while(!(que.empty())){//队列非空时，持续进行遍历操作，当队列为空的时候说明所有的节点元素均已弹出
        	int size = que.size();
            vector<int> temp;
        	while(size--){
            	TreeNode* node = que.front();
            	que.pop();
            	temp.push_back(node->val);
            	if(node->left)	que.push(node->left);
            	if(node->right)	que.push(node->right);
        	}
            res.push_back(temp);
        }
        return res;
    }
};
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

力扣107题二叉树的层序遍历Ⅱ

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

107.二叉树的层次遍历II

代码如下：
1

/**
 * 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>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if(root != NULL)    que.push(root);
        else return res;
        while(!(que.empty())){
            int size = que.size();
            vector<int> temp;
            while(size--){
                TreeNode* node = que.front();
            	que.pop();
            	temp.push_back(node->val);
            	if(node->left)	que.push(node->left);
                if(node->right)	que.push(node->right);
            }
            res.push_back(temp);
        }
        reverse(res.begin(),res.end());//只需要添加reverse函数即可
        return res;
    }
};
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

力扣199题二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

199.二叉树的右视图

代码如下：

/**
 * 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> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> res;
        if(root != NULL)	que.push(root);
        else return res;
        while(!(que.empty())){
        	int size = que.size();
            vector<int> temp;
        	while(size--){
            	TreeNode* node = que.front();
            	que.pop();
            	temp.push_back(node->val);
                if(node->left) que.push(node->left);
            	if(node->right)	que.push(node->right);                
        	}
            int last = temp.back();//由于只看最右边的元素，所以是每层最右侧的节点元素
            res.push_back(last);
        }
        return res;
    }
};
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

力扣637题二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

637.二叉树的层平均值

代码如下：

/**
 * 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:
	// double GetAverage(vector<int> vec){
    //     double sum = 0;        
    //     for(int i = 0; i < vec.size(); i++){

    //         sum = sum + vec[i];
    //     }
    //     double ave = sum/vec.size();
    //     return ave;
    // };
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> que;//定义队列来存放二叉树节点
        vector<double> res;
        if(root != NULL)	que.push(root);
        else return res;
        while(!(que.empty())){//队列非空时，持续进行遍历操作，当队列为空的时候说明所有的节点元素均已弹出
        	int size = que.size();
            double sum = 0;
        	for(int i = 0;i < size; i++){
            	TreeNode* node = que.front();
            	que.pop();
            	sum += node->val;
            	if(node->left)	que.push(node->left);
            	if(node->right)	que.push(node->right);
        	}
            res.push_back(sum / size);//无须额外定义求平均值的函数，直接push_back即可
        }
        return res;
    }
};
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

力扣429题 N叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

例如，给定一个 3叉树 :

429. N叉树的层序遍历

返回其层序遍历:

[ [1], [3,2,4], [5,6] ]

代码如下：

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;//此处修改了树节点的定义，每个节点下面可以有多个用数组存放的子节点

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;//定义队列来存放二叉树节点
        vector<vector<int>> res;//定义二维数组来存放每一层的节点
        if(root != NULL)	que.push(root);
        else return res;
        while(!(que.empty())){//队列非空时，持续进行遍历操作，当队列为空的时候说明所有的节点元素均已弹出
        	int size = que.size();
            vector<int> temp;
        	while(size--){
            	Node* node = que.front();
            	que.pop();
            	temp.push_back(node->val);
                for(int i = 0; i < node->children.size();i++){
                    if(node->children[i])   que.push(node->children[i]);
                }
        	}
            res.push_back(temp);
        }
        return res;
    }
};
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

力扣515题在每个栈中找最大值

您需要在二叉树的每一行中找到最大的值。

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) {
        queue<TreeNode*> que;//定义队列来存放二叉树节点
        vector<int> res;
        if(root != NULL)	que.push(root);
        else return res;
        while(!(que.empty())){//队列非空时，持续进行遍历操作，当队列为空的时候说明所有的节点元素均已弹出
        	int size = que.size();
            int MaxNum = INT_MIN;//取最小值进行比较，得到每一层的最大值
        	for(int i = 0; i < size; i++){
            	TreeNode* node = que.front();
            	que.pop();
            	MaxNum = MaxNum > node->val ? MaxNum : node->val;
            	if(node->left)	que.push(node->left);
            	if(node->right)	que.push(node->right);
        	}
            res.push_back(MaxNum);
        }
        return res;
    }
};
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

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

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
1
2
3
4
5
6

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

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

和之前不一样的是，这里的头节点需要特殊处理，提前取出来，其他所有的节点处理方式一样；

具体代码实现如下：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root != NULL) que.push(root);
        else return NULL;
        while(!(que.empty())){
            int size = que.size();
            Node* node;
            Node* nodePre;
            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 = nodePre->next;
                }
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
            nodePre->next = 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

这道题，写的时候人麻了……

这能卡我半个小时的……

记录下来思维卡壳状态下的思路：

将当前节点node的next指针指向nodePre；

再将nodePre更新为当前节点node，即nodePre = nodePre->next;

但是这里为什么叫nodePre前一个节点？？？以例子为例的话第二次for循环处理以后，第一次得到的node是元素值为2的节点，那这个节点的前一个节点是什么？不应该没有东西吗？

很简单啊……

nodePre存放的地址不会因为else语句的结束而被清除，nodePre的声明在循环外面，这个nodePre实际起的作用是一个临时存储指针node_temp的作用；所以nodePre完成对第一个层内节点的存储以后，再次进入for循环的时候nodePre存储的就是第一个层内节点，这样就能够实现左右节点相链接从而达到题目要求。

力扣117题填充每个节点的下一个右侧节点指针Ⅱ

除了不是完美二叉树以外，和上道题思路代码都是一致，不再赘述。

力扣104题二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

104. 二叉树的最大深度

返回它的最大深度 3

很简单的题，深度优先遍历，depth++：

class Solution{
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        int depth = 0;
        if(root == NULL)	return 0;
        que.push(root);
        while(!(que.empty())){
            int size = que.size();
            depth++; // 记录深度
            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);
        	}
        }
        return depth;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

力扣111题二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2
1
2

一样的思路，但是返回条件不同，最大深度是所有的节点的叶节点均为空的时候返回；而最小深度是再第一次遍历到叶节点均为空的时候就直接return；

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录最小深度
            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 depth;
                }
            }
        }
        return depth;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

翻转二叉树

搞清楚自己代码实现的逻辑底层是什么！

先用递归实现：

1.确定递归函数的返回值和参数：TreeNode* ReverseTree(TreeNode* root){};

2.确定遍历终止条件：if(root == NULL) return root;

3.确认单层递归逻辑：

前序遍历：中左右；

处理逻辑：swap(root->left,root->right)//此处root指的是遍历的每一个节点，不是根节点

即：

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

后序遍历：左右中；

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        invertTree(root->left);         // 左
        invertTree(root->right);        // 右
        swap(root->left, root->right);  // 中
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10

中序呢，左中右行吗？

可以实现类似于中序的写法，但是实际操作是“左中左”；

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        invertTree(root->left);         // 左
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 左
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10

其余的写法明天再补吧，今天有点累了；

对称二叉树

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

示例 1：

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

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false
1
2

还是确定遍历顺序，不要稀里糊涂！

由于这道题需要不断对比左右孩子的信息返回给上一个节点，才能知道左右节点是否是相互翻转的；

只有后序遍历，才能将左右孩子的信息返回回上一层;

1.确认递归函数类型和返回值：bool compare(TreeNode* left , TreeNode* right);

2.确定终止条件：

要么左子树为空，右子树不为空 return false;

要么右子树为空，左子树不为空 return false;

要么左右都不为空 return true;

要么左右都不为空但不等 return false;

要么左右都不为空且相等执行第三步单层递归逻辑；

3.单层递归逻辑：

我们需要对左子树和右子树的子节点进行比较：外侧和内侧

bool outside = compare(left->left , right->right); //左子树：左右子树：右

bool inside = compare(left->right , right->left); //左子树：右右子树：左

bool res = outside && inside; //左子树：中右子树：中

则可以得到递归函数：

    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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

整体代码如下：

/**
 * 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:
    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 false;
        bool res = compare(root->left,root->right);
        return res;
    }
};

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/387039

Day 15 层序遍历 226.翻转二叉树 101.对称二叉树

层序遍历

力扣102题，层序遍历

力扣107题 二叉树的层序遍历Ⅱ

力扣199题 二叉树的右视图

力扣637题 二叉树的层平均值

力扣429题 N叉树的层序遍历

力扣515题 在每个栈中找最大值

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

力扣117题 填充每个节点的下一个右侧节点指针Ⅱ

力扣104题 二叉树的最大深度

力扣111题 二叉树的最小深度

翻转二叉树

对称二叉树

力扣107题二叉树的层序遍历Ⅱ

力扣199题二叉树的右视图

力扣637题二叉树的层平均值

力扣515题在每个栈中找最大值

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

力扣117题填充每个节点的下一个右侧节点指针Ⅱ

力扣104题二叉树的最大深度

力扣111题二叉树的最小深度