226.翻转二叉树
思路
递归轻松AC
现在多思考一步，是不是这个函数模板如TreeNode* invertTree(TreeNode* root)可以适用于每一小部分
翻转过程：
题解
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == nullptr)return nullptr;
TreeNode* temp = invertTree(root->left);
root->left = invertTree(root->right);
root->right = temp;
return root;
}
};
101.对称二叉树
题目链接：101.对称二叉树
状态：思路错误，没写出来
思路
递归解决，难点在于读题和创造一个新的函数bool isSymmetry(TreeNode* left, TreeNode* right)
对称二叉树，关键点在于中心对称，即只有根节点的左右子树对称，左子树的左右子树不一定对称啊！！！
那么题目给的函数模板isSymmetric是判断根root节点左右是否对称的，很明显不能写出递归，要另起炉灶
根节点中心对称问题转化为->左右子树对称，即left->left,right->right与left->right,right->left分别相等
待补充···
题解
class Solution {
public:
bool isSymmetry(TreeNode* left, TreeNode* right)
{
if(left == nullptr && right == nullptr)return true;
else if(left != nullptr && right != nullptr)
{
if(left->val == right->val)return isSymmetry(left->left,right->right)&&isSymmetry(left->right,right->left);
else return false;
}
else return false;
}
bool isSymmetric(TreeNode* root) {
return isSymmetry(root->left,root->right);
}
};
104.二叉树的最大深度
题目链接：104.二叉树的最大深度
文档讲解：代码随想录
状态：遍历轻松AC
思路
递归三部曲轻松解决，注意与二叉树的最小深度的对比思考
题解
class Solution {
public:
// 第一种递归：递归遍历，并使用数组保存深度
// void find(TreeNode* root,vector<int> &vec,int depth)
// {
// if(root == nullptr)return ;
// vec.push_back(depth);
// find(root->left, vec,depth+1);
// find(root->right,vec,depth+1);
// }
// int maxDepth(TreeNode* root) {
// vector<int> vec;
// find(root,vec,1);
// if(root!=nullptr)
// {
// auto max = max_element(vec.begin(),vec.end());
// return *max;
// }
// else return 0;
// }
//第二种递归，抓住求左右子树深度
int maxDepth(TreeNode* root) {
if(root == nullptr)return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return left>right?(left+1):(right+1);
}
};
111.二叉树的最小深度
题目链接：111.二叉树的最小深度
文档讲解：代码随想录
状态：没理解题意，蒙了
思路
本质在于：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
故对于最小深度，不是简单取左右子树最小值，有左右子树取最小，若左右子树其中一个为空，则取另外一边
因此，正确的做法是：
- 如果当前节点是叶子节点（即左右子节点都为空），则深度为1。
- 如果当前节点只有一侧子树为空，则不能考虑空子树，应该只考虑非空子树的深度。
- 如果当前节点左右子树都不为空，则取左右子树深度的较小值。
欠理解···
题解
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == nullptr) return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
if(root->left!=nullptr && root->right!=nullptr)
{
return left<right?(left+1):(right+1);
}
else
{
return left>right?(left+1):(right+1);
}
}
};