本文主要是介绍代码随想录训练营第十五天 110平衡二叉树 257二叉树的所有路径 404左子树之和 222完全二叉树的节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第一题：
原题链接：110. 平衡二叉树 - 力扣（LeetCode）
首先什么事平衡二叉树：平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 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:bool isBalanced(TreeNode* root) {return height(root) == -1 ? false : true;}
private:int height(TreeNode* node){if(node == 0) return 0;int LeftHeight = height(node -> left);if(LeftHeight == -1) return -1;int rightHeight = height(node -> right);if(rightHeight == -1) return -1;return abs(rightHeight - LeftHeight) > 1 ? -1 : 1 + max(LeftHeight, rightHeight);}
};第二题：
原题链接：257. 二叉树的所有路径 - 力扣（LeetCode）
这道题是看了视频才会做的。一开始思路是正确的，在实现添加“->”这个的时候出了问题，回溯没搞好。
使用回溯的方法：
本题使用前序遍历的方式，中左右。
当当前节点的左右节点都为的空的情况下证明这是一条完整的路径了，可以直接添加“->”然后加入res中。
先将中的节点元素添加进path中，然后向左和向右递归。在向左和向右递归之后要紧接着回溯。将元素弹出。
代码如下：
class Solution {
private:void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {path.push_back(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中 // 这才到了叶子节点if (cur->left == NULL && cur->right == NULL) {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);return;}if (cur->left) { // 左 traversal(cur->left, path, result);path.pop_back(); // 回溯}if (cur->right) { // 右traversal(cur->right, path, result);path.pop_back(); // 回溯}}public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> path;if (root == NULL) return result;traversal(root, path, result);return result;}
};第三题：
原题链接：404. 左叶子之和 - 力扣（LeetCode）
思路：
参数和返回值都很好定义出来，参数就是根节点，返回值就是左叶子之和。
我们使用前序遍历的方式，那么当我们找到一个左叶子的时候，res加上该叶子的值即可。最后返回res。在找的时候要主要先判断当前节点的左节点是否存在，如果不存在的话判断条件就失效了。
代码如下：
/*** 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 res = 0;int sumOfLeftLeaves(TreeNode* node) {if(node -> left != nullptr && node -> left -> left == nullptr && node -> left -> right == nullptr){res += node -> left -> val;}if(node -> left) sumOfLeftLeaves(node -> left);if(node -> right) sumOfLeftLeaves(node -> right);return res;}
};第四题：
原题链接：222. 完全二叉树的节点个数 - 力扣（LeetCode）
思路：
使用前序遍历的方式一直遍历，遇到节点就+1即可。
终止条件是当root为空的时候，返回0；
代码如下：
/*** 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 res = 0;int countNodes(TreeNode* root) {if(root == nullptr) return 0;res += 1;if(root -> left) countNodes(root -> left);if(root -> right) countNodes(root -> right);return res;}
};这篇关于代码随想录训练营第十五天 110平衡二叉树 257二叉树的所有路径 404左子树之和 222完全二叉树的节点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
