代码随想录day17

110. 平衡二叉树

递归法：

 1 class Solution {
 2 public:
 3     //递归三步走
 4     //1、确定返回值和函数参数
 5     int getHeight(TreeNode* node){
 6         //2、明确终止条件
 7         if (node == nullptr) return 0;
 8         //3、明确单层递归的逻辑
 9         int leftHeight = getHeight(node->left);
10         if (leftHeight == -1) return -1;
11         int rightHeight = getHeight(node->right);
12         if (rightHeight == -1) return -1;
13         int result;
14         if (abs(leftHeight - rightHeight) > 1) return -1;
15         else result = 1 + max(leftHeight, rightHeight);
16         return result;
17     }
18     bool isBalanced(TreeNode* root) {
19         return getHeight(root) == -1 ? false : true;
20     }
21 };

257. 二叉树的所有路径

 1 class Solution {
 2 private:
 3 
 4     void traversal(TreeNode* cur, string path, vector<string>& result) {
 5         path += to_string(cur->val); // 中
 6         if (cur->left == NULL && cur->right == NULL) {
 7             result.push_back(path);
 8             return;
 9         }
10         if (cur->left) traversal(cur->left, path + "->", result); // 左
11         if (cur->right) traversal(cur->right, path + "->", result); // 右
12     }
13 
14 public:
15     vector<string> binaryTreePaths(TreeNode* root) {
16         vector<string> result;
17         string path;
18         if (root == NULL) return result;
19         traversal(root, path, result);
20         return result;
21 
22     }
23 };

404. 左叶子之和

 1 class Solution {
 2 public:
 3     int sumOfLeftLeaves(TreeNode* root) {
 4         int result = 0;
 5         queue<TreeNode*> que;
 6         if (root != nullptr) que.push(root);
 7         while (!que.empty()){
 8             int size = que.size();
 9             while (size--){
10                 TreeNode* node = que.front();
11                 que.pop();
12                 if (node->left != nullptr && node->left->left == nullptr && node->left->right == nullptr) result += node->left->val;
13                 if (node->left) que.push(node->left);
14                 if (node->right) que.push(node->right);
15             }
16         }
17         return result;
18     }
19 };