当前位置: 首页 > news >正文

代码随想录算法训练营Day14 | 226.翻转二叉树、101. 对称二叉树、104.二叉树的最大深度、111.二叉树的最小深度

文章目录

  • 226.翻转二叉树
    • 思路与重点
  • 101. 对称二叉树
    • 思路与重点
  • 104.二叉树的最大深度
    • 思路与重点
  • 111.二叉树的最小深度
    • 思路与重点


226.翻转二叉树

  • 题目链接:226. 翻转二叉树 - 力扣(LeetCode)
  • 讲解链接:代码随想录
  • 状态:一遍AC。

思路与重点

  • 注意只要把每一个节点的左右孩子翻转一下就可以达到整体翻转的效果,使用前序遍历和后序遍历都可以,唯独中序遍历不方便,因为中序遍历会把某些节点的左右孩子翻转了两次!建议拿纸画一画,就理解了。
  • 那么层序遍历可以不可以呢?依然可以的!只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的!
class Solution {
public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val);    // 中traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

101. 对称二叉树

  • 题目链接:101. 对称二叉树 - 力扣(LeetCode)
  • 讲解链接:代码随想录
  • 状态:一遍AC。

思路与重点

  • 可以采用层序遍历,每一层去看是不是对称的。注意对于空着的节点,需要赋值101来进行比较
class Solution {
public:bool isSymmetric(TreeNode* root) {bool ans = true;queue<TreeNode*> q;if(root) q.push(root);while(!q.empty()){vector<int> v;int size = q.size();for(int i = 0; i < size; i++){TreeNode* node = q.front();q.pop();if(!node) v.push_back(101);else v.push_back(node->val);if(node){q.push(node->left);q.push(node->right);}}for(int i = 0; i < size/2 ; i++){if(v[i] != v[size - i - 1]){ans = false;break;}}if(!ans) break;}return ans;}
};
  • 对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了其实我们要比较的是两个树(这两个树是根节点的左右子树),所以在递归遍历的过程中,也是要同时遍历两棵树。
  • 也可以使用递归的做法:
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;else return compare(left->left, right->right) && compare(left->right, right->left);}bool isSymmetric(TreeNode* root) {if (root == NULL) return true;return compare(root->left, root->right);}
};
  • 或者使用迭代:
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;}// 左右一个节点不为空,或者都不为空但数值不相同,返回falseif ((!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;}
};

104.二叉树的最大深度

  • 题目链接:104. 二叉树的最大深度 - 力扣(LeetCode)
  • 讲解链接:代码随想录
  • 状态:一遍AC。

思路与重点

  • 层序遍历模板题。
class Solution {
public:int maxDepth(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);}}return depth;}
};
  • 用递归也可以解决:
class Solution {
public:int maxDepth(TreeNode* root) {if(!root) return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}
};

111.二叉树的最小深度

  • 题目链接:111. 二叉树的最小深度 - 力扣(LeetCode)
  • 讲解链接:代码随想录
  • 状态:一遍AC。

思路与重点

  • 层序遍历模板题。
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;}
};
  • 前序遍历和后序遍历都可以,前序求的是深度,后序求的是高度
  • 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)
  • 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数后者节点数(取决于高度从0开始还是从1开始)
  • 递归解决:求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
    int minDepth(TreeNode* root) {if(!root) return 0;int leftDepth = minDepth(root->left);int rightDepth = minDepth(root->right);if(leftDepth == 0 && rightDepth != 0) return rightDepth + 1;else if(leftDepth != 0 && rightDepth == 0) return leftDepth + 1;else return min(leftDepth, rightDepth) + 1;}


http://www.mrgr.cn/news/70595.html

相关文章:

  • openresty入门教程:rewrite_by_lua_block
  • 【NLP优化】Ubuntu 20.04 下 源码安装 CasADi + Ipopt / acados
  • glide ModelLoader的Key错误使用 可能造成的内存泄漏
  • 基于Python+Django+Vue3+MySQL实现的前后端分类的商场车辆管理系统
  • ECharts 实现大屏地图功能
  • Java多线程详解⑦(全程干货!!!)内存可见性 || volatile || JMM || wait notify notifyAll
  • 信息安全数学基础(47)域的结构
  • PCL 点云分割 分割圆柱体模型
  • PCL 点云分割 分割指定平面
  • 功率板布局布线进阶【一】
  • 以太网的发展
  • 大数据学习12之HBase
  • Chrome如何查看保存的网站密码,如此简单!
  • 使用PsExec工具
  • java双向链表解析实现双向链表的创建含代码
  • 仅想要实现一个网站登录者之间可以进行临时会话的功能, 需要几张数据表? 人工ai替你回答(ai版)
  • 全网最详细的自动化测试(Jenkins 篇)
  • 算法学习第一弹——C++基础
  • 在线绘制带community的蛋白质-蛋白质相互作用(PPI)网络图
  • 【JAVA】-WEB开发基础
  • 牛客周赛 Round 67
  • UE5遇到问题记录
  • More Effective C++:异常
  • C++builder中的人工智能(21):Barabási–Albert model(BA)模型
  • Snipaste截图软件直接运行
  • 【Web前端】从回调到现代Promise与Async/Await