题目：翻转二叉树
思路：使用递归的方式使用前序或后序的方式来进行操作，在每一个节点出都使用swap来将左右子树进行调转（有时间可以模拟以下过程）
每次做到这道题一定要想一下为什么不能用中序
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == nullptr) return root;
swap(root->left,root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};题目：对称二叉树
101. 对称二叉树 - 力扣（LeetCode）（考察两个二叉树同时遍历的能力）
这道题做完后必须要直到的一个点，如果需要从根节点搜集信息不断往上传播的题目必须使用后续遍历的方式，“左右中”的遍历方式的中可以理解为数据收集所在的位置。
思路：从递归三部曲上考虑
返回值：bool
遍历的终值条件：左值为空右值为空返回true，左值为空右值不为空返回false，左值不为空右值为空返回false，左值不等于右值返回false，左值等于右值则进入递归三部曲第三步
单层递归逻辑：判断外侧的值是否相等，判断内侧的值是否相等，若外侧和内侧都相等返回true，否则返回false。
class Solution {
public:
bool compare(TreeNode*left, TreeNode*right)
{
if(left == nullptr && right == nullptr) return true;
else if(left != nullptr && right == nullptr) return false;
else if(left == nullptr && right != nullptr) return false;
else if(left->val != right->val) return false;
bool outside = compare(left->left,right->right);
bool inside = compare(left->right ,right->left);
bool reslut = outside && inside;
return reslut;
}
bool isSymmetric(TreeNode* root) {
return compare(root->left,root->right);
}
};题目：二叉树的最大深度
思路：从递归三部曲上考虑
返回值：左右子树的最大层数
遍历的终值条件：如果到了根节点即可终值
单层递归逻辑：选出左右子树的最大值上传
因为本体和上体一样需要从根节点获取信息因此也需要使用后续遍历的方式
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == nullptr) return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
int cur = max(left, right) +1; //加1是为了记录本层的层数
return cur;
}
};题目：二叉树的最小深度
思路：在做这道题时候有很多小细节在一开始没有考虑到，还拿上面题目的方法做，结果失败了。本体最大的不同是因为需要考虑左右节点只有一个的情况，因此需要全方位的考虑这个问题（写这题感觉就是在打补丁🤣）
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == nullptr) return 0;
if(root->left == nullptr && root->right == nullptr) return 1;
if(root->left != nullptr && root->right == nullptr)
{
int left = minDepth(root->left);
left++;
return left;
}
if(root->left == nullptr && root->right != nullptr)
{
int right = minDepth(root->right);
right ++;
return right;
}
int left = minDepth(root->left);
int right = minDepth(root->right);
int cur = min(left,right) + 1;
return cur;
}
};
评论