110. 平衡二叉树
思路
比较高度适合用后序遍历，前序遍历时间复杂度高。
实现
点击查看代码
class Solution {
public:
bool isBalanced(TreeNode* root) {
return getDepth(root) >= 0;
}
int getDepth(TreeNode* cur){
if(cur == nullptr)return 0;
int left = getDepth(cur->left);
int right = getDepth(cur->right);
if(left == -1 || right == -1 || abs(left-right) >1){
return -1;
}
else{
return 1+max(left,right);
}
}
};
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
257. 二叉树的所有路径
1.递归+路径
思路
1.这道题的难点在于递归和回溯的混合使用。
2.在访问完一个节点之后，要对这个节点进行回溯。
3.如果使用记录路径的方法，通过访问节点结束后对path栈顶元素的弹出可以实现回溯
实现
点击查看代码
/**
* 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:
vector<string> binaryTreePaths(TreeNode* root) {
vector<int> path;
vector<string> result;
traversal(root,path,result);
return result;
}
void traversal(TreeNode* cur,vector<int>& path, vector<string>& result){
if(cur->left == nullptr && cur->right == nullptr){
string s;
for(int i = 0; i < path.size(); i++){
s += to_string(path[i]) + "->";
}
s += to_string(cur->val);
result.push_back(s);
}
path.push_back(cur->val);
if(cur->left){
traversal(cur->left,path,result);
path.pop_back();
}
if(cur->right){
traversal(cur->right,path,result);
path.pop_back();
}
}
};
复杂度分析
- 时间复杂度：O(n^2)
- 空间复杂度：O(n^2)
2.递归+string
思路
1.通过传string值而非引用来实现回溯
2.传入string+"->"的方式非常巧妙
实现
点击查看代码
/**
* 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:
vector<string> binaryTreePaths(TreeNode* root) {
string s;
vector<string> result;
traversal(root,s,result);
return result;
}
void traversal(TreeNode* cur, string s, vector<string>& result){
s += to_string(cur->val);
if(cur->left == nullptr && cur->right == nullptr){
result.push_back(s);
return;
}
if(cur->left)traversal(cur->left,s+"->",result);
if(cur->right)traversal(cur->right,s+"->",result);
}
};
复杂度分析
- 时间复杂度：O(n^2),每次传入节点时，都要对string进行拷贝构造，拷贝构造的时间复杂度为O(n);
- 空间复杂度：O(n^2) ,如果二叉树是链状，那么需要复制n个string,空间复杂度为O(n^2);如果是平衡二叉树，那么空间复杂度为 O(logN^2)。
3.迭代
思路
通过使用栈存储string来达到回溯的作用。
实现
点击查看代码
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
stack<TreeNode*> st;
vector<string> result;
stack<string> path;
if(root == nullptr)return result;
st.push(root);
while(!st.empty()){
TreeNode* cur = st.top();
st.pop();
string s;
if(!path.empty()){
s = path.top();
path.pop();
}
s += to_string(cur->val);
if(cur->left == nullptr && cur->right == nullptr){
result.push_back(s);
}
if(cur->left){
st.push(cur->left);
path.push(s + "->");
}
if(cur->right){
st.push(cur->right);
path.push(s + "->");
}
}
return result;
}
};
404. 左叶子之和
1.后序遍历+递归
思路
1.判断一个节点是不是左叶子要通过其父节点来判断，如果是其父节点的左孩子且没有子节点，那么是一个左叶子。
2.要计算左叶子之和用后序遍历比较方便。
实现
点击查看代码
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(root == nullptr)return 0;
int leftValue = sumOfLeftLeaves(root->left);
if(root->left && !root->left->left && !root->left->right){
leftValue = root->left->val;
}
int rightValue =sumOfLeftLeaves(root->right);
int sum = leftValue + rightValue;
return sum;
}
};
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)