代码随想录算法训练营第十五天（一）| 110.平衡二叉树 （优先掌握递归）257. 二叉树的所有路径
110.平衡二叉树
题目：
给定一个二叉树，判断它是否是 平衡二叉树
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false
示例 3：
输入：root = [] 输出：true
提示：
- 树中的节点数在范围
[0, 5000]内 -104 <= Node.val <= 104
思路：
首先了解一下概念：平衡二叉树
平衡二叉树（Balanced Binary Tree）是指一棵二叉树中每个节点的左右子树的高度差不超过1。换句话说，二叉树中的任意节点的左右子树的高度差最多为1，并且左右子树本身也是一棵平衡二叉树。
要判断一棵二叉树是否是平衡二叉树，可以使用递归的方法来检查每个节点的左右子树的高度差。如果某个节点的左右子树高度差超过1，那么这棵树就不是平衡二叉树。
递归的思路：
- 对于每个节点，递归地计算它的左右子树的高度。
- 如果某个节点的左右子树的高度差超过1，返回
false。 - 如果所有节点的左右子树高度差都不超过1，返回
true。
上代码：
/*** 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 height(TreeNode* root) {// 如果当前节点为空，返回高度0if (root == nullptr) return 0;// 递归计算左子树的高度int leftHeight = height(root->left);// 如果左子树不平衡，直接返回-1if (leftHeight == -1) return -1;// 递归计算右子树的高度int rightHeight = height(root->right);// 如果右子树不平衡，直接返回-1if (rightHeight == -1) return -1;// 判断当前节点是否平衡if (abs(leftHeight - rightHeight) > 1) {return -1; // 不平衡返回-1}// 返回当前节点的高度return max(leftHeight, rightHeight) + 1;}// 主函数：判断二叉树是否平衡bool isBalanced(TreeNode* root) {// 调用辅助函数，如果高度函数返回-1，表示不平衡return height(root) != -1;}
};
257. 二叉树的所有路径
题目：
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
示例 2：
输入：root = [1] 输出：["1"]
提示：
- 树中节点的数目在范围
[1, 100]内 -100 <= Node.val <= 100
思路：
要找出二叉树中所有从根节点到叶子节点的路径，我们可以使用深度优先搜索（DFS）的方法进行遍历。在遍历过程中，记录从根节点到当前节点的路径，当到达叶子节点时，将这条路径记录下来。
递归思路：
- 使用递归函数
dfs，从根节点开始，沿着每一条路径进行深度优先搜索。 - 在每次递归调用中，将当前节点的值添加到路径中。
- 如果当前节点是叶子节点（没有左子树和右子树），将路径转换为字符串并存储到结果列表中。
- 如果当前节点有子节点，继续递归遍历其子节点，传递当前路径。
- 最后返回结果列表。
上代码:
/*** 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:// 辅助函数：使用DFS遍历每条从根到叶子节点的路径void dfs(TreeNode* node, string path, vector<string>& paths) {if (!node)return; // 如果节点为空，直接返回// 将当前节点的值加入到路径中path += to_string(node->val);// 如果当前节点是叶子节点，则将路径添加到结果列表中if (!node->left && !node->right) {paths.push_back(path);} else {// 如果不是叶子节点，继续向下遍历，并在路径中添加 "->"path += "->";dfs(node->left, path, paths);dfs(node->right, path, paths);}}vector<string> binaryTreePaths(TreeNode* root) {vector<string> paths;if (root) {dfs(root, "", paths); // 从根节点开始进行DFS}return paths;}
};