树03

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 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;if(abs(leftHeight - rightHeight) > 1)return -1;else{return max(leftHeight, rightHeight) + 1;}}bool isBalanced(TreeNode* root) {int height = getHeight(root);if(height == -1) return false;else return true;}
};

257. 二叉树的所有路径

/*** 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:void preOrder(TreeNode* node, vector<string> &result, string s){s += to_string(node-> val);if (node->left == NULL && node->right == NULL) {result.push_back(s);return;}if(node->left)preOrder(node->left, result, s + "->");if(node->right)preOrder(node->right, result, s + "->");}vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;if(root == nullptr) return result;string s = "";preOrder(root, result, s);return result;}
};

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:void PreOrder(TreeNode* node, int &sum){if(node -> left != nullptr && node->left->left == nullptr && node->left->right == nullptr){sum += node->left->val;// if(node->right) PreOrder(node->right, sum);// return;}if(node->left) PreOrder(node->left, sum);if(node->right) PreOrder(node->right, sum);}int sumOfLeftLeaves(TreeNode* root) {int sum = 0;if(root) {PreOrder(root, sum);return sum;}else return sum;}
};

513. 找树左下角的值

/*** 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 findBottomLeftValue(TreeNode* root) {int result;queue<TreeNode*> que;if(root == nullptr) return 0;que.push(root);while(!que.empty()){int size = que.size();int mSize = size;while(size--){TreeNode* cur = que.front();que.pop();if(size == mSize - 1)result = cur->val;if(cur->left)que.push(cur->left);if(cur->right)que.push(cur->right);}}return result;}
};