打卡第17天，补卡中，懒狗又歇了几天。

今日任务

• 110.平衡二叉树
• 257.二叉树的所有路径
• 404.左叶子之和

110.平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

代码随想录

后序遍历求高度，如果遇到左右高度相差大于1，返回-1，做标记，直接结束。

class Solution {
public:int getHight(TreeNode* root) {if(root == NULL) return 0;int lHight = getHight(root->left);if(lHight == -1) return -1;int rHight = getHight(root->right);if(rHight == -1) return -1;return abs(lHight - rHight) > 1 ? -1 : max(rHight, lHight) + 1;}bool isBalanced(TreeNode* root) {return getHight(root) == -1 ? false: true;}
};

257.二叉树的所有路径

给你一个二叉树的根节点root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。

我的题解

不知道怎么绕出来了。

class Solution {
public:void work(TreeNode *node, vector > &res,vector &path) {//递归出口if(node == nullptr) return ;//访问结点，收集结点path.push_back(node->val);//左work(node->left, res, path);//右work(node->right, res, path);if(node->left == nullptr && node->right == nullptr) {//收集答案res.push_back(path);}//回溯弹出收集的结点path.pop_back();}vector binaryTreePaths(TreeNode* root) {vector > res;vector path;work(root, res, path);vector str(res.size());for(int i = 0; i < res.size(); i++) {for(int j = 0; j < res[i].size(); j++) {if(j != 0) str[i] += "->";str[i] += to_string(res[i][j]);}}return str;}
};

代码随想录

我们需要遍历来保存每一个结点，记录路径，回溯回退一个路径进入另一个路径。

class Solution {
public:void traversal(TreeNode* node, vector &path, vector &res) {path.push_back(node->val); //中，收集结点// 到叶子结点，收集结构，出口if(node->left == NULL && node->right == NULL) {string sPath;for(int i = 0; i < path.size(); i++) {if(i != 0) sPath += "->";sPath += to_string(path[i]);}res.push_back(sPath);return ;}//左if(node->left) {traversal(node->left, path, res); //一直递归path.pop_back(); //回溯，回退结点} //右if(node->right) {traversal(node->right, path, res); //一直递归path.pop_back(); //回溯，回退结点} }vector binaryTreePaths(TreeNode* root) {vector res;vector path;if(root) traversal(root, path, res);return res;}
};

404.左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

代码随想录

递归法

1. 确定递归函数的参数和返回值
   判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int。使用题目中给出的函数就可以了。
2. 确认递归出口，当传入结点为空，说明左叶子指一定为空。

   if(root == NULL) return 0;
   

   注意，只有当前遍历的节点是父节点，才能判断其子节点是不是左叶子。 所以如果当前遍历的节点是叶子节点，那其左叶子也必定是0，那么终止条件为：

   if(root == NULL) return 0;	
   if(root->left == NULL && root->right == NULL) return 0;
   

3. 确定单层递归的逻辑
   当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if(root == nullptr) return 0;int l = sumOfLeftLeaves(root->left);if(root->left && !root->left->left && !root->left->right) l += root->left->val; int r = sumOfLeftLeaves(root->right);return l + r;}
};

迭代法

本题迭代法使用前中后序都是可以的，只要把左叶子节点统计出来，就可以了。

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {stack st;if (root == NULL) return 0;st.push(root);int result = 0;while (!st.empty()) {TreeNode* node = st.top();st.pop();if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {result += node->left->val;}if (node->right) st.push(node->right);if (node->left) st.push(node->left);}return result;}
};

这道题目要求左叶子之和，其实是比较绕的，因为不能判断本节点是不是左叶子节点。

此时就要通过节点的父节点来判断其左孩子是不是左叶子了。

平时我们解二叉树的题目时，已经习惯了通过节点的左右孩子判断本节点的属性，而本题我们要通过节点的父节点判断本节点的属性。