【LC刷题】DAY12:226 144 94 145
226. 翻转二叉树 link
/**
* 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:
TreeNode* invertTree(TreeNode* root) {
if(!root){
return root ;
}
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
101. 对称二叉树 link
/**
* 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 == nullptr && right != nullptr) return false;
else if (left != nullptr && right == nullptr) return false;
else if (left == nullptr && right == nullptr) 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){
return false;
}
return compare(root->left, root->right);
}
};
104. 二叉树的最大深度
/**
* 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 maxDepth(TreeNode* root) {
if(!root){
return 0;
}
queue<TreeNode*> q;
q.push(root);
int depth = 0;
while(!q.empty()){
int size = q.size();
for(int i = 0; i< size; i ++){
auto node = q.front();
q.pop();
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
depth++;
}
return depth;
}
};
559. N 叉树的最大深度 link
/*
// 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:
int maxDepth(Node* root) {
if(root==nullptr){
return 0;
}
queue<Node*> q;
q.push(root);
int depth = 0;
while(!q.empty()){
int size = q.size();
for(int i =0 ; i < size; i ++){
auto node = q.front();
q.pop();
for(auto n : node->children ){
q.push(n);
}
}
depth++;
}
return depth;
}
};
111. 二叉树的最小深度 link
/**
* 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 minDepth(TreeNode* root) {
if(!root){
return 0;
}
queue<TreeNode*> q;
q.push(root);
int depth = 1;
while(!q.empty()){
int size = q.size();
for(int i =0; i < size; i++){
auto node = q.front();
q.pop();
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
if(!node->left && !node->right){
return depth;
}
}
depth++;
}
return depth;
}
};