题目：
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
想法：
肯定是要遍历，那就用递归法，==这里总结一下心得，用递归法深度遍历就要考虑哪种遍历顺序，根据就是要做什么处理，比如这道题，要判断子树的信息，那就是后序遍历。==定义递归函数的意义：返回以传入节点为根节点的树的高度。一个细节就是判断是否为高度平衡二叉树，用-1表示不是，如果子节点不是高度平衡二叉树，那当前的节点也肯定不是了，算是一个小优化。然后就是本节点的处理：要算上当前节点，也就是高度+1再返回。
/**
* 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 getHeight(TreeNode* node) {
//终止条件 走到了空节点 返回高度0
if (node == nullptr) {
return 0;
}
//如果不是空节点，获取以子节点为根节点的树的高度，判断是否满足平衡二叉树，如果不满足，没有必要再计算
int leftHeight = getHeight(node -> left);
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node -> right);
if (rightHeight == -1) return -1;
//用-1代表不满足平衡二叉树
if (abs(leftHeight - rightHeight) > 1) return -1;
//如果满足平衡二叉树，返回以传入节点为根节点的树的高度
return max(leftHeight, rightHeight) + 1;
}
bool isBalanced(TreeNode* root) {
int result = getHeight(root);
if (result == -1) return false;
return true;
}
};
题目：
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
想法：
这里提及了回溯算法。我的理解就是有递归就要有回溯，但是是有前提的，前提就是只有当递归以后改变了传入参数的信息，并且传入参数在本次递归中还需要利用的就需要回溯，也就是把修改的内容去除掉。对于传值而非传递引用的递归函数就不需要回溯了。回溯只需要考虑递归一层以后的结果，不需要继续向下考虑，因为回溯操作在递归函数里，下一层的递归所需要的回溯在下一层递归函数里解决。
还有就是讲解中对于版本二的代码的讲解我认为有点问题，讲解中认为"->“是需要回溯的，但我认为不是真正意义的回溯，只是在本层处理中向下递归的入参不能错，而向我下面代码写的那样，”->"的添加放在if语句的外面就可以了，本质上pop操作的原因并不是递归引起的。
/**
* 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:
void traversal(TreeNode* node, vector<int>& path, vector<string>& result) {
//处理当前节点
path.push_back(node -> val);
//终止条件
if (!node -> left && !node -> right) {
//把path转化为一个结果放入result
string s;
//因为要加"->"，最后一个要单独处理
for (int i = 0; i < path.size() - 1; i++) {
s += to_string(path[i]);
s += "->";
}
s += to_string(path[path.size() - 1]);
result.push_back(s);
return ;
}
//递归+回溯
if (node -> left) {
traversal(node -> left, path, result);
//此时path，result都被改变了，为了递归右节点，需要pop掉，
//path加内容只考虑一层，因为这个函数是递归函数，在下一次调用的时候也会考虑到下下层的递归
path.pop_back();
}
//因为对于上一层的递归，path在这里也被改了，所以为了上一层能返回正常结果，这里也要pop掉
if (node -> right) {
traversal(node -> right, path, result);
path.pop_back();
}
return ;
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
traversal(root, path, result);
return result;
}
};
//版本二
// class Solution {
// private:
// void traversal(TreeNode* cur, string path, vector<string>& result) {
// path += to_string(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中
// if (cur->left == NULL && cur->right == NULL) {
// result.push_back(path);
// return;
// }
// path += "->";
// if (cur->left) {
// traversal(cur->left, path, result); // 左
// // path.pop_back(); // 回溯 '>'
// // path.pop_back(); // 回溯 '-'
// }
// if (cur->right) {
// // path += "->";
// traversal(cur->right, path, result); // 右
// // path.pop_back(); // 回溯'>'
// // path.pop_back(); // 回溯 '-'
// }
// }
// public:
// vector<string> binaryTreePaths(TreeNode* root) {
// vector<string> result;
// string path;
// if (root == NULL) return result;
// traversal(root, path, result);
// return result;
// }
// };
题目：
给定二叉树的根节点 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:
//思路：递归法
//明确左叶子的定义，即判断条件 当前节点有左子节点，且该左子节点不含左右子节点
int sumOfLeftLeaves(TreeNode* root) {
//定义返回值类型为int为当前节点的所有左叶子之和 入参为当前节点，所以用题目给的函数作为递归函数即可
//终止条件
if (root == nullptr) {
return 0;
}
//当前节点的处理逻辑 如何计算当前节点的左叶子之和
//递归计算当前节点的左子节点的左叶子之和，然后是右子节点的左叶子之和，加在一起
int leftSum = sumOfLeftLeaves(root -> left);
int rightSum = sumOfLeftLeaves(root -> right);
//还有一部分就是判断左子节点本身是不是一个左叶子，如果是把该节点的值也加上
if (root -> left && !root -> left -> left && !root -> left -> right) {
return leftSum + rightSum + root -> left -> val;
}
return leftSum + rightSum;
}
};