day17打卡

110. 平衡二叉树

• 递归法
• 时间复杂度：O(N)，空间复杂度：O(N)

class Solution {
public:int getHeight(TreeNode* root){if(root == nullptr) return 0;int leftHeight = getHeight(root->left);if(leftHeight == -1) return -1;int rightHeight = getHeight(root->right);if(rightHeight == -1) return -1;if(abs(leftHeight - rightHeight) > 1)return -1;elsereturn max(leftHeight, rightHeight) + 1;}bool isBalanced(TreeNode* root) {return getHeight(root) != -1;}
};

• 迭代法
• 时间复杂度：O(N)，空间复杂度：O(N)

暂时不写，后面补

257. 二叉树的所有路径

• 递归法

• 时间复杂度：O(N)，空间复杂度：O(N)

class Solution {
public://记录结果vector<string> ret;vector<string> binaryTreePaths(TreeNode* root) {//记录路径string path = "";dfs(root, path);return ret;}//path设置在参数处，我们就不用关心回溯了void dfs(TreeNode* root, string path){if(root->left == nullptr && root->right == nullptr){path += to_string(root->val);ret.push_back(path);return;}else{path += to_string(root->val) + "->";}if(root->left) dfs(root->left, path);if(root->right) dfs(root->right, path);}
};

• 迭代法
• 时间复杂度：O(N)，空间复杂度：O(N)

class Solution {
public:vector<string> binaryTreePaths(TreeNode* root) {stack<TreeNode*> treeSt;stack<string> pathSt;vector<string> ret;if(root != nullptr){treeSt.push(root);pathSt.push(to_string(root->val));}while(!treeSt.empty()){TreeNode* top = treeSt.top();treeSt.pop();string path = pathSt.top();pathSt.pop();if(top->left == nullptr && top->right == nullptr){ret.push_back(path);}if(top->left) {treeSt.push(top->left);pathSt.push(path + "->" + to_string(top->left->val));}if(top->right) {treeSt.push(top->right);pathSt.push(path + "->" + to_string(top->right->val));}}return ret;}
};

404. 左叶子之和

• 递归法
• 时间复杂度：O(N)，空间复杂度：O(N)

class Solution {
public://记录和int sum = 0;int sumOfLeftLeaves(TreeNode* root) {dfs(root);return sum;}void dfs(TreeNode* root){if(root == nullptr) return;//判断是否是左叶子节点if(root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr)sum += root->left->val;if(root->left) dfs(root->left);if(root->right) dfs(root->right);}
};

• 迭代法
• 时间复杂度：O(N)，空间复杂度：O(N)

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {stack<TreeNode*> st;if(root != nullptr) st.push(root);int sum = 0;while(!st.empty()){TreeNode* top = st.top();st.pop();if(top->left != nullptr && top->left->left == nullptr && top->left->right == nullptr)sum += top->left->val;if(top->left) st.push(top->left);if(top->right) st.push(top->right);}return sum;}
};