代码随想录刷题题Day12

2023-12-13 20:13:42

刷题的第十二天，希望自己能够不断坚持下去，迎来蜕变。😀😀😀
刷题语言：C++
Day12 任务
● 层序遍历 10
● 226.翻转二叉树
● 101.对称二叉树 2

1 层序遍历

一口气做十题
102.二叉树的层序遍历
 107.二叉树的层次遍历II
199.二叉树的右视图
 637.二叉树的层平均值
 429.N叉树的层序遍历
 515.在每个树行中找最大值
 116.填充每个节点的下一个右侧节点指针
 117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
 111.二叉树的最小深度

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。
队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑

在这里插入图片描述
102.二叉树的层序遍历

层序遍历模板：
C++：

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();
			vector<int> vec;
			// 这里一定要使用固定大小size，不要使用que.size()
			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);
		}
		return result;
    }
};

107.二叉树的层次遍历II
在这里插入图片描述

思路：

把result数组反转一下

C++：

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

199.二叉树的右视图
在这里插入图片描述
思路：

判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result

C++：

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();
            for (int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                que.pop();
                if (i == (size - 1)) result.push_back(node->val);// 将每一层的最后元素放入result数组
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

637.二叉树的层平均值
在这里插入图片描述
思路：

层序遍历的时候把一层求个总和在取一个均值

C++：

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> que;
        vector<double> result;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            double sum = 0;// 统计每一层的和
            int size = que.size();
            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);
            }
            result.push_back(sum / size);// 将每一层均值放进结果
        }
        return result;
    }
};

429.N叉树的层序遍历
在这里插入图片描述
思路：

一个节点有多个孩子,用for循环

C++：

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;
        vector<vector<int>> result;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            vector<int> vec;
            while (size--)
            {
                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;
    }
};

515.在每个树行中找最大值
在这里插入图片描述
思路：

层序遍历，取每一层的最大值

C++：

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> result;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            int maxValue = INT_MIN;// 取每一层的最大值
            for (int i = 0; i < size; i++)
            {
                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;
    }
};

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> result;
        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);
            }
            auto MAX = max_element(vec.begin(), vec.end());
            result.push_back(*MAX);
        }
        return result;
    }
};

116.填充每个节点的下一个右侧节点指针
在这里插入图片描述
思路：

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

C++：

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

117.填充每个节点的下一个右侧节点指针II
在这里插入图片描述
思路：

和上个题目一样

C++：

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

104.二叉树的最大深度
在这里插入图片描述
思路：

使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数。在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度

C++：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        int depth = 0;
        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) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return depth;
    }
};

111.二叉树的最小深度
在这里插入图片描述
思路：

当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

C++：

class Solution {
public:
    int minDepth(TreeNode* root) {
        int depth = 0;
        queue<TreeNode*> que;
        if (root == NULL) return 0;
        else 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;
    }
};

2 翻转二叉树

在这里插入图片描述
思路：

把每一个节点的左右孩子交换一下。注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果

递归法：
在这里插入图片描述
（1）确定递归函数的参数和返回值

参数：要传入节点的指针
返回值：其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为TreeNode*

TreeNode* invertTree(TreeNode* root)

（2）确定终止条件

if (root == NULL) return root;

（3）确定单层递归的逻辑
前序遍历：中左右

swap(root->left, root->right);
invert(root->left);
invert(root->right);

中序遍历：左中右

invert(root->left);
swap(root->left, root->right);
invert(root->left);

后序遍历：左右中

invert(root->left);
invert(root->right);
swap(root->left, root->right);

针对二叉树的问题，解题之前一定要想清楚究竟是前中后序遍历，还是层序遍历

C++：

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

迭代法：
深度优先遍历
C++：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty())
        {
            TreeNode* node = st.top();// 中
            st.pop();
            swap(node->left, node->right);
            if (node->right) st.push(node->right);// 右
            if (node->left) st.push(node->left);// 左
        }
        return root;
    }
};

广度优先遍历

层数遍历也是可以翻转这棵树的，因为层序遍历也可以把每个节点的左右孩子都翻转一遍

C++：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            while (size--)
            {
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right);// 节点处理
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return root;
    }
};

3 对称二叉树

在这里插入图片描述
思路：

比较的是根节点的左子树与右子树是不是相互翻转的,比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。

在这里插入图片描述
比较的是两个子树的里侧和外侧的元素是否相等
遍历顺序只能是后序遍历，因为要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中
递归法：
（1）确定递归函数的参数和返回值
比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
返回值自然是bool类型

bool compare(TreeNode* left, TreeNode* right)

（2）确定终止条件
要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。

左节点为空，右节点不为空，不对称，return false
左不为空，右为空，不对称 return false
左右都为空，对称，返回true
左右都不为空，比较节点数值，不相同就return false

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;

（3）确定单层递归的逻辑
处理左右节点都不为空，且数值相同的情况

比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
如果左右都对称就返回true ，有一侧不对称就返回false 。

bool outside = compare(left->left, right->right); // 左子树：左、 右子树：右
bool inside = compare(left->right, right->left);// 左子树：右、 右子树：左
bool result = outside && inside;// 左子树：中、 右子树：中
return result;

C++：

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 result = outside && inside;
        return result;
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

鼓励坚持十三天的自己😀😀😀

文章来源:https://blog.csdn.net/BigDavid123/article/details/134970812
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！