LeetCode热题100刷题9：25. K 个一组翻转链表、101. 对称二叉树、543. 二叉树的直径、102. 二叉树的层序遍历

25. K 个一组翻转链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverse(ListNode* a, ListNode* b) {ListNode* pre=nullptr;ListNode* cur = a;ListNode* nxt = a;while(cur!=b) {nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}return pre;}ListNode* reverseKGroup(ListNode* head, int k) {if(head==nullptr)return nullptr;ListNode* a = head;ListNode* b = head;for(int i=0;i<k;i++) {if(b==nullptr)return head;b=b->next;}ListNode* newHead = reverse(a,b);a->next = reverseKGroup(b,k);return newHead;}
};

101. 对称二叉树

/*** 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(!right && !left)return true;if(left && !right)return false;if(right && !left)return false;if(left->val != right->val)return false;bool l = compare(left->left,right->right);bool r = compare(left->right,right->left);return l&&r;}bool isSymmetric(TreeNode* root) {if(!root)return true;return compare(root->left,root->right);}
};

543. 二叉树的直径

/*** 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:int ans;int depth(TreeNode* root) {if(!root)return 0;int left = depth(root->left);int right = depth(root->right);ans = max(ans,left+right);return max(left,right)+1;}int diameterOfBinaryTree(TreeNode* root) {ans=0;depth(root);return ans;}
};

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)return res;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!=NULL)que.push(node->left);if(node->right!=NULL)que.push(node->right);}res.push_back(vec);}return res;}
};