代码随想录算法训练营第十五天| 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和、 222.完全二叉树的节点个数

本文主要是介绍代码随想录算法训练营第十五天| 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和、 222.完全二叉树的节点个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode110.平衡二叉树

题目链接：110. 平衡二叉树

C++：(后序遍历)

class Solution {
public:int getheight(TreeNode *node){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;//中int result;if(abs(leftheight - rightheight) > 1)result = -1;else{result = 1 + max(leftheight, rightheight);}return result;}bool isBalanced(TreeNode* root) {return getheight(root) == -1 ? false : true;}
};

Python：

class Solution:def getheight(self, node):if node == None:return 0leftheight = self.getheight(node.left)if leftheight == -1:return -1rightheight = self.getheight(node.right)if rightheight == -1:return -1if abs(leftheight - rightheight) > 1:result = -1else:result = 1 + max(leftheight, rightheight)return resultdef isBalanced(self, root: Optional[TreeNode]) -> bool:return False if self.getheight(root) == -1 else True

Leetcode257. 二叉树的所有路径

题目链接：257. 二叉树的所有路径

C++：(回溯算法初体验)

注意：传入的形参为引用格式，递归+回溯成对出现

class Solution {
public:void findway(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);return;}//左if(node->left != nullptr){findway(node->left, path, result);path.pop_back();  //回溯}//右if(node->right != nullptr){findway(node->right, path, result);path.pop_back();  //回溯}}vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> path;if (root == NULL) return result;findway(root, path, result);return result;}
};

Python：

map()函数：会根据提供的函数对指定序列做映射，语法：map(function, iterable)

     （1)function：函数

       (2) iterable：一个或多个序列

class Solution:def findway(self, node, path, result):# zhongpath.append(node.val)if node.left == None and node.right == None:sPath = '->'.join(map(str, path))result.append(sPath)returnif node.left:self.findway(node.left, path, result)path.pop()if node.right:self.findway(node.right, path, result)path.pop()def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:path = []result = []if root == None:return resultself.findway(root, path, result)return result

Leetcode404.左叶子之和

题目链接：404. 左叶子之和

C++：

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if(root == nullptr) return 0;if(root->left == nullptr && root->right == nullptr) return 0;//zuoint Leftsum = sumOfLeftLeaves(root->left);if(root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr)Leftsum = root->left->val;//youint Rightsum = sumOfLeftLeaves(root->right);//zhongint sum = Leftsum + Rightsum;return sum;}
};

Leetcode 222.完全二叉树的节点个数

题目链接：222. 完全二叉树的节点个数

完全二叉树的结点数量可以通过满二叉树结点数量公式计算：2**depth - 1

C++：

class Solution {
public:int countNodes(TreeNode* root) {//后序遍历if(root == nullptr) return 0;auto left = root->left;int leftdepth = 0;auto right = root->right;int rightdepth = 0;while(left){left = left->left;leftdepth++;}while(right){right = right->right;rightdepth++;}if(leftdepth == rightdepth)return (2 << leftdepth) - 1;//zuoint leftnum = countNodes(root->left);//youint rightnum = countNodes(root->right);//zhongint num = leftnum + rightnum + 1;return num;}
};

这篇关于代码随想录算法训练营第十五天| 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和、 222.完全二叉树的节点个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---