1.力扣226:翻转二叉树
题目描述:
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3] 输出：[2,3,1]
示例 3：
输入：root = [] 输出：[]
解答代码:
/**
* 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 == NULL) return root;
// swap(root->left, root->right);
// if(root->left) invertTree(root->left);
// if(root->right) invertTree(root->right);
if(root->left) invertTree(root->left);
if(root->right) invertTree(root->right);
swap(root->left, root->right);
return root;
}
};代码逻辑:
这个代码实现了一个递归函数 'maxDepth' 来计算二叉树的最大深度。它采用后序遍历的方法，递归地计算每个节点左右子树的深度，并返回其中较大的值加一，作为当前节点的深度。以下是代码的逐步解释：
代码讲解
'''cpp
class Solution {
public:
int maxDepth(TreeNode root) {
if (root == NULL) return 0; // 如果节点为空，返回深度 0
// 后序遍历
int leftsize = maxDepth(root->left); // 左：递归计算左子树的深度
int rightsize = maxDepth(root->right); // 右：递归计算右子树的深度
return max(leftsize, rightsize) + 1; // 中：选择左右子树较大值加1，表示当前节点的深度
}
};
'''
解释
1. 终止条件：当 'root == NULL'，即遍历到叶子节点的下一层时，返回深度为 0。
2. 递归过程：依次递归计算左右子树的深度 'leftsize' 和 'rightsize'。
3. 返回值：每层递归返回左右子树深度中的最大值加 1，以得到该节点的深度。
示例
对于以下二叉树：
'''
3
/ \
9 20
/ \
15 7
'''
调用 'maxDepth' 会输出 '3'，因为该树的最大深度是 3。
2.力扣101:对称二叉树
题目描述:
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
解答代码:
/**
* 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 == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;
bool outside = compare(left->left, right->right);
bool inside = compare(left->right, right->left);
return outside && inside;
}
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
bool result = compare(root->left, root->right);
return result;
}
};代码逻辑:
代码用于判断二叉树是否对称，即是否是镜像对称的。代码通过递归的 'compare' 函数，对比二叉树左右子树的结构和节点值来判断树的对称性。
代码说明
1. compare 函数：递归比较 'left' 和 'right' 两棵子树是否是镜像对称的。判断逻辑如下：
- 若一边为空而另一边不为空，返回 'false'。
- 若两边都为空，返回 'true'。
- 若两节点的值不相等，返回 'false'。
- 若以上条件均满足，递归检查子节点的对称性。
- 'outside'：递归比较 'left->left' 和 'right->right'。
- 'inside'：递归比较 'left->right' 和 'right->left'。
- 最终，'outside' 和 'inside' 同时为 'true' 时，当前节点对称。
2. isSymmetric 函数：若 'root' 为空，直接返回 'true'。否则调用 'compare' 函数检查 'root' 左右子树的对称性。
时间复杂度
时间复杂度为 \(O(n)\)，其中 \(n\) 是树中节点的数量，因为每个节点会被访问一次。
示例
对于输入 '[1, 2, 2, 3, 4, 4, 3]'，'isSymmetric' 函数会返回 'true'，因为该树是对称的。
3.力扣104:二叉树的最大深度
题目描述：
定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：
输入：root = [1,null,2] 输出：2
解答代码：
/**
* 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 == NULL) return 0;
// 后序遍历
int leftsize = maxDepth(root->left); // 左
int rightsize = maxDepth(root->right); // 右
return max(leftsize, rightsize) + 1; // 中
}
};代码逻辑:
代码实现了一个递归函数 'maxDepth' 来计算二叉树的最大深度。采用了后序遍历的方法，递归地计算每个节点左右子树的深度，并返回其中较大的值加一，作为当前节点的深度。以下是代码的逐步解释：
代码讲解
'''cpp
class Solution {
public:
int maxDepth(TreeNode root) {
if (root == NULL) return 0; // 如果节点为空，返回深度 0
// 后序遍历
int leftsize = maxDepth(root->left); // 左：递归计算左子树的深度
int rightsize = maxDepth(root->right); // 右：递归计算右子树的深度
return max(leftsize, rightsize) + 1; // 中：选择左右子树较大值加1，表示当前节点的深度
}
};
'''
解释
1. 终止条件：当 'root == NULL'，即遍历到叶子节点的下一层时，返回深度为 0。
2. 递归过程：依次递归计算左右子树的深度 'leftsize' 和 'rightsize'。
3. 返回值：每层递归返回左右子树深度中的最大值加 1，以得到该节点的深度。
示例
对于以下二叉树：
'''
3
/ \
9 20
/ \
15 7
'''
调用 'maxDepth' 会输出 '3'，因为该树的最大深度是 3。
4.力扣111:二叉树的最小深度
题目描述:
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
解答代码:
/**
* 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 == NULL) return 0;
// 后续遍历
int leftheight = minDepth(root->left); //左
int rightheight = minDepth(root->right); //右
// 处理节点为空的情况
if (root->left == NULL && root->right != NULL)
return rightheight + 1;
if (root->right == NULL && root->left != NULL)
return leftheight + 1;
int result = min(leftheight, rightheight) + 1;
return result;
}
};求最小深度的时候注意处理左节点或者右节点为空的情况
代码逻辑
代码定义了一个递归函数 'minDepth' 来计算二叉树的最小深度。它通过后序遍历的方式递归计算左右子树的最小深度，并处理了当某一子树为空时的特殊情况。
代码说明
1. 边界条件：若 'root' 为空，则返回 '0'，表示树的深度为 '0'。
2. 后序遍历：对左右子树分别调用 'minDepth' 函数计算其深度。
3. 处理单子树情况：当左子树或右子树为空时，只返回另一子树的深度 +1。
4. 返回最小深度：当左右子树都不为空时，返回左右子树深度的较小值加 '1'。
时间复杂度
时间复杂度为 (O(n))，其中 (n) 是树中节点的数量，因为每个节点会被访问一次。