小山菌_代码随想录算法训练营第十七天|110.平衡二叉树、257. 二叉树的所有路径（优先掌握递归）、 404.左叶子之和

本文主要是介绍小山菌_代码随想录算法训练营第十七天|110.平衡二叉树、257. 二叉树的所有路径（优先掌握递归）、 404.左叶子之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

110.平衡二叉树

文档讲解：代码随想录.平衡二叉树
视频讲解：后序遍历求高度，高度判断是否平衡 | LeetCode：110.平衡二叉树
状态：已完成

代码实现

/*** 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 getGight(TreeNode* node) {if (node == nullptr)return 0;int left_hight = getGight(node->left);//左if (left_hight == -1)return -1;int right_hight = getGight(node->right);//右if (right_hight == -1)return -1;if (abs(left_hight - right_hight) > 1) {//中return -1;}int result = 1 + max(right_hight, left_hight);return result;}bool isBalanced(TreeNode* root) {return getGight(root) == -1 ? false : true;}
};

心得记录：

1.对于递归的三要素中的函数入口，终止条件右一定的理解了，但是单层的循环条件还是有点模糊，尤其是不同情况下的前中后序的选择。
2. 因为求深度可以从上到下去查所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

257. 二叉树的所有路径（优先掌握递归）

文档讲解：代码随想录二叉树的所有路径（优先掌握递归
视频讲解：后序遍历求高度，高度判断是否平衡 | LeetCode：110.平衡二叉树
状态：已完成

代码实现

/*** 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 {
private:void getPath(TreeNode* node, vector<int>& path, vector<string>& result) {// 中path.push_back(node->val);if (node->left == nullptr && node->right == nullptr) {string spath;for (int i = 0; i < path.size() - 1; i++) {spath += to_string(path[i]);spath += "->";}spath += to_string(path[path.size() - 1]);result.push_back(spath);}// 左if (node->left) {getPath(node->left, path, result);path.pop_back(); // 回溯，把vector中最后一个删除}// 右if (node->right) {getPath(node->right, path, result);path.pop_back(); // 回溯，把vector中最后一个删除}}public:vector<string> binaryTreePaths(TreeNode* root) {vector<int> path;vector<string> result;if (root == nullptr)return result;getPath(root, path, result);return result;}
};

心得记录：

1.回溯的使用有了初步的理解，比较灵巧，这里只对最基本的方法进行了理解

404.左叶子之和

文档讲解：代码随想录.左叶子之和
视频讲解：二叉树的题目中，总有一些规则让你找不到北 | LeetCode：404.左叶子之和
状态：已完成

代码实现

/*** 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) {if (root == NULL) return 0;if (root->left == NULL && root->right== NULL) return 0;int leftValue = sumOfLeftLeaves(root->left);    // 左if (root->left && !root->left->left && !root->left->right) { // 左子树就是一个左叶子的情况leftValue = root->left->val;}int rightValue = sumOfLeftLeaves(root->right);  // 右int sum = leftValue + rightValue;               // 中return sum;}
};