devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

代码随想录算法训练营第十五天 | 层序遍历 226.翻转二叉树 101.对称二叉树

作者：小小林熬夜学编程 | 2024-06-05 03:07:09

赞

踩

代码随想录算法训练营第十五天 | 层序遍历 226.翻转二叉树 101.对称二叉树

day15 记录代码随想录

层序遍历

力扣102 二叉树的层序遍历

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12.  /*写一下结构体链表
  13.  struct tree{
  14.     int val;
  15.     tree* left;
  16.     tree* right;
  17.     tree(int x) : val(x),left(NULL),right(NULL) {}
  18.  };
  19.  */
  20. class Solution {
  21. public:
  22.     vector<vector<int>> levelOrder(TreeNode* root) {
  23.         vector<vector<int>> result;
  24.         queue<TreeNode*> que;
  25.         if(root != NULL) que.push(root);
  26.         while(!que.empty()) {
  27.             int size = que.size();
  28.             vector<int> floor;
  29.             while(size--) {
  30.                 if(que.front()->left != NULL) que.push(que.front()->left);
  31.                 if(que.front()->right != NULL) que.push(que.front()->right);
  32.                 floor.push_back(que.front()->val);
  33.                 que.pop();
  34.             }
  35.             result.push_back(floor);
  36.         }
  37.         return result;
  38.     }
  39. };

力扣107 二叉树的层序遍历II

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<vector<int>> levelOrderBottom(TreeNode* root) {
  15.         vector<vector<int>> result;
  16.         queue<TreeNode*> que;
  17.         if(root != NULL)    que.push(root);
  18.         while(!que.empty()) {
  19.             vector<int> floor;
  20.             int size = que.size();
  21.             while(size--) {
  22.                 TreeNode* node;
  23.                 node = que.front();
  24.                 if( node->right != NULL) que.push(node->right);
  25.                 if( node->left != NULL) que.push(node->left);
  26.                 floor.push_back(node->val);
  27.                 que.pop();
  28.             }
  29.             reverse(floor.begin(),floor.end());
  30.             result.push_back(floor);
  31.         }
  32.         reverse(result.begin(),result.end());
  33.         return result;
  34.     }
  35. };

力扣199 二叉树的右视图

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

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<int> rightSideView(TreeNode* root) {
  15.         vector<int> result;
  16.         queue<TreeNode*> que;
  17.         if(root == NULL) return result;
  18.         que.push(root);
  19.         while(!que.empty()) {
  20.             int size;
  21.             vector<int> floor;
  22.             size = que.size();
  23.             while(size--) {
  24.                 TreeNode* cur = que.front();
  25.                 if(cur->right)   que.push(cur->right);
  26.                 if(cur->left)   que.push(cur->left);
  27.                 floor.push_back(cur->val);
  28.                 que.pop();
  29.             }
  30.             result.push_back(floor[0]);
  31.         }
  32.         return result;
  33.     }
  34. };

力扣637 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<double> averageOfLevels(TreeNode* root) {
  15.         vector<double> result;
  16.         queue<TreeNode*> que;
  17.         if(root == NULL) return result;
  18.         que.push(root);
  19.         while(!que.empty()) {
  20.             int size = que.size();
  21.             int c = size;
  22.             double sum = 0;
  23.             while(size--) {
  24.                 TreeNode* cur = que.front();
  25.                 if(cur->left)   que.push(cur->left);
  26.                 if(cur->right)  que.push(cur->right);
  27.                 que.pop();
  28.                 sum += cur->val;
  29.             }
  30.             result.push_back(sum/c);
  31.         }
  32.         return result;
  33.     }
  34. };

力扣429 N叉树的层序遍历

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

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     vector<Node*> children;
  8.     Node() {}
  10.     Node(int _val) {
  11.         val = _val;
  12.     }
  14.     Node(int _val, vector<Node*> _children) {
  15.         val = _val;
  16.         children = _children;
  17.     }
  18. };
  19. */
  20.  
  21. class Solution {
  22. public:
  23.     vector<vector<int>> levelOrder(Node* root) {
  24.         vector<vector<int>> result;
  25.         if(root == NULL)    return result;
  26.         queue<Node*> que;
  27.         que.push(root);
  28.         while(!que.empty()) {
  29.             vector<int> floor;
  30.             int size = que.size();
  31.             while(size--) {
  32.                 Node* cur = que.front();
  33.                 for(int i = 0; i < cur->children.size(); i++) {
  34.                     que.push(cur->children[i]);
  35.                 }
  36.                 floor.push_back(cur->val);
  37.                 que.pop();
  38.             }
  39.             result.push_back(floor);
  40.         }
  41.         return result;
  42.     }
  43. };

力扣515 在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<int> largestValues(TreeNode* root) {
  15.         vector<int> result;
  16.         queue<TreeNode*> que;
  17.         if(root == NULL) return result;
  18.         que.push(root);
  19.         while(!que.empty()) {
  20.             int max = que.front()->val;
  21.             int size = que.size();
  22.             while(size--) {
  23.                 TreeNode* cur = que.front();
  24.                 if(cur->left)   que.push(cur->left);
  25.                 if(cur->right)  que.push(cur->right);
  26.                 if(cur->val > max)  max = cur->val;
  27.                 que.pop();
  28.             }
  29.             result.push_back(max);
  30.         }
  31.         return result;
  32.     }
  33. };

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

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

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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

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

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     Node* left;
  7.     Node* right;
  8.     Node* next;
  10.     Node() : val(0), left(NULL), right(NULL), next(NULL) {}
  12.     Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
  14.     Node(int _val, Node* _left, Node* _right, Node* _next)
  15.         : val(_val), left(_left), right(_right), next(_next) {}
  16. };
  17. */
  18.  
  19. class Solution {
  20. public:
  21.     Node* connect(Node* root) {
  22.         if(root == NULL) return NULL;
  23.         queue<Node*> que;
  24.         que.push(root);
  25.         while(!que.empty()) {
  26.             int size = que.size();
  27.             while(size--) {
  28.                 Node* cur = que.front();
  29.                 if(cur->left)   que.push(cur->left);
  30.                 if(cur->right)  que.push(cur->right);
  31.                 que.pop();
  32.                 if(size == 0)
  33.                     cur->next = NULL;
  34.                 else
  35.                     cur->next = que.front();
  36.             }
  37.         }
  38.         return root;
  39.     }
  40. };

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

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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

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

emmm，写这个的时候发现上一题代码一样。

力扣104 二叉树的最大深度

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int maxDepth(TreeNode* root) {
  15.         if(root == NULL)    return 0;
  16.         queue<TreeNode*> que;
  17.         que.push(root);
  18.         int depth = 0;
  19.         while(!que.empty()) {
  20.             int size = que.size();
  21.             while(size--) {
  22.                 TreeNode* cur = que.front();
  23.                 if(cur->left)   que.push(cur->left);
  24.                 if(cur->right)  que.push(cur->right);
  25.                 que.pop();
  26.             }
  27.             depth++;
  28.         }
  29.         return depth;
  30.  
  31.     }
  32. };

力扣111 二叉树的最小深度

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

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

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

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int minDepth(TreeNode* root) {
  15.         if(root == NULL)    return 0;
  16.         queue<TreeNode*> que;
  17.         int depth = 0;
  18.         que.push(root);
  19.         while(1) {
  20.             int size = que.size();
  21.             depth++;
  22.             while(size--) {
  23.                 TreeNode* cur = que.front();
  24.                 que.pop();
  25.                 if(!cur->left && !cur->right) return depth;
  26.                 else {
  27.                     if(cur->left)   que.push(cur->left);
  28.                     if(cur->right)  que.push(cur->right);
  29.                 }
  30.             }
  31.              
  32.         }
  33.         return 0;
  34.     }
  35. };

第二题 力扣226 翻转二叉树

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

题目链接：226. 翻转二叉树

解题思路：

递归函数三步：传入参数、终止条件、单次循环

递归法

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12.  //递归
  13. class Solution {
  14. public:
  15.     TreeNode* invertTree(TreeNode* root) {
  16.         TreeNode* cur = root;
  17.         if(cur == NULL)    return cur;
  18.         swap(cur->left,cur->right);
  19.         invertTree(cur->left);
  20.         invertTree(cur->right);
  21.         return root;
  22.     }
  23. };

迭代法 

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12.  //迭代
  13. class Solution {
  14. public:
  15.     TreeNode* invertTree(TreeNode* root) {
  16.         if(root == NULL)    return NULL;
  17.         stack<TreeNode*> st;
  18.         st.push(root);
  19.         while(!st.empty()) {
  20.             TreeNode* cur = st.top();
  21.             st.pop();
  22.             swap(cur->left,cur->right);
  23.             if(cur->left)   st.push(cur->left);   
  24.             if(cur->right)  st.push(cur->right);
  25.         }
  26.         return root;
  27.     }
  28. };

第二题 力扣101 对称二叉树

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

题目链接：力扣题目链接

递归法

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     bool compare(TreeNode* left, TreeNode* right) {
  15.         if(left == NULL && right == NULL)   return 1;
  16.         else if(left != NULL && right == NULL) return 0;
  17.         else if(left == NULL && right != NULL) return 0;
  18.         else if(left->val != right->val) return 0;
  19.         else {
  20.             bool l = compare(left->left, right->right);
  21.             bool r = compare(left->right, right->left);
  22.             return l&&r;
  23.         }
  24.     }
  25.  
  26.     bool isSymmetric(TreeNode* root) {
  27.         if(root == NULL)    return 1;
  28.         return compare(root->left, root->right);
  29.     }
  30. };

迭代法

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12.  //迭代法
  13. class Solution {
  14. public:
  15.     bool isSymmetric(TreeNode* root) {
  16.         if(root == NULL)    return 1;
  17.         queue<TreeNode*> que;
  18.         que.push(root->left);
  19.         que.push(root->right);
  20.         while(!que.empty()) {
  21.             TreeNode* left = que.front();
  22.             que.pop();
  23.             TreeNode* right = que.front();
  24.             que.pop();
  25.             if(left == NULL && right == NULL)   continue;
  26.             else if(left == NULL || right == NULL || left->val != right->val)
  27.                 return 0;
  28.             else    
  29.                 que.push(left->left);
  30.                 que.push(right->right);
  31.                 que.push(left->right);
  32.                 que.push(right->left);
  33.         }
  34.         return 1;
  35.     }
  36. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/674548
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号