110. 平衡二叉树 - 力扣（LeetCode）
思路:遍历每个节点，如果该节点左右子树相差大于1则返回false，如果全部符合条件则返回true
我的AC代码
//时间复杂度O(n2),空间复杂度O(n2)
class Solution {
public:
int get_depth(TreeNode* node) {
if(node == nullptr) {
return 0;
}
int left = get_depth(node->left);
int right = get_depth(node->right);
return 1 + max(left, right);
}
bool judge(TreeNode* node) {
if(node == nullptr) {
return true;
}
return judge(node->left) && judge(node->right) && abs(get_depth(node->left) - get_depth(node->right)) <= 1;
}
bool isBalanced(TreeNode* root) {
if(root == nullptr) {
return true;
}
return judge(root);
}
};标准答案
递归法(后序遍历)
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1
int getHeight(TreeNode* node) {
if (node == NULL) {
return 0;
}
int leftHeight = getHeight(node->left);
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node->right);
if (rightHeight == -1) return -1;
return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
return getHeight(root) == -1 ? false : true;
}
};迭代法(模拟后序遍历)
//时间复杂度O(n2),空间复杂度O(n2)
class Solution {
private:
int getDepth(TreeNode* cur) {
stack<TreeNode*> st;
if (cur != NULL) st.push(cur);
int depth = 0; // 记录深度
int result = 0;
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
st.push(node); // 中
st.push(NULL);
depth++;
if (node->right) st.push(node->right); // 右
if (node->left) st.push(node->left); // 左
} else {
st.pop();
node = st.top();
st.pop();
depth--;
}
result = result > depth ? result : depth;
}
return result;
}
public:
bool isBalanced(TreeNode* root) {
stack<TreeNode*> st;
if (root == NULL) return true;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
if (abs(getDepth(node->left) - getDepth(node->right)) > 1) {
return false;
}
if (node->right) st.push(node->right); // 右（空节点不入栈）
if (node->left) st.push(node->left); // 左（空节点不入栈）
}
return true;
}
};257. 二叉树的所有路径 - 力扣（LeetCode）
思路:用递归前序遍历二叉树，每遇到一个节点就将节点值加入路径中，然后判断该节点左右两侧是否还有孩子，如果有则用此时的路径值创建一个新的字符串带入递归函数，否则宣告该路径走到尽头，将答案填入数组ans中，此思路中回溯的方法就是创建一个新的字符串
技巧：做好回溯的关键是：注意到回溯和递归是一一对应的，有一个递归，就要有一个回溯
理论上下面的几种方法使用的空间复杂度都是接近的，但是貌似因为递归法要调用系统堆栈所以空间占用略大于迭代法
我的AC代码
递归法(直接创建新字符串不回溯)
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
void findall(TreeNode* node, vector<string>& ans, string& s) {
if(node->left == nullptr && node->right == nullptr) {
string b = s + to_string(node->val);
ans.push_back(b);
}
string a = s + to_string(node->val);
a += "->";
if(node->left) {
findall(node->left, ans, a);
}
if(node->right) {
findall(node->right, ans, a);
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ans;
string s = "";
findall(root, ans, s);
return ans;
}
};复刻标准答案迭代法(前序遍历)
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
stack<TreeNode*> st;
stack<string> path;
vector<string> ans;
if(root == nullptr) {
return ans;
}
st.push(root);
string a = to_string(root->val);
path.push(a);
while(!st.empty()) {
TreeNode* tmp = st.top();
st.pop();
string stmp = path.top();
path.pop();
if(!tmp->left && !tmp->right) {
ans.push_back(stmp);
}
if(tmp->left) {
st.push(tmp->left);
path.push(stmp + "->" + to_string(tmp->left->val));
}
if(tmp->right) {
st.push(tmp->right);
path.push(stmp + "->" + to_string(tmp->right->val));
}
}
return ans;
}
};标准答案
递归版本一
//时间复杂度O(n),空间复杂度O(n)
// 版本一
class Solution {
private:
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
path.push_back(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中
// 这才到了叶子节点
if (cur->left == NULL && cur->right == NULL) {
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 (cur->left) { // 左
traversal(cur->left, path, result);
path.pop_back(); // 回溯
}
if (cur->right) { // 右
traversal(cur->right, path, result);
path.pop_back(); // 回溯
}
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}
};递归版本二
//时间复杂度O(n),空间复杂度O(n)
// 版本二
class Solution {
private:
void traversal(TreeNode* cur, string path, vector<string>& result) {
path += to_string(cur->val); // 中
if (cur->left == NULL && cur->right == NULL) {
result.push_back(path);
return;
}
if (cur->left) traversal(cur->left, path + "->", result); // 左
if (cur->right) traversal(cur->right, path + "->", result); // 右
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
string path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}
};递归版本三
//时间复杂度O(n),空间复杂度O(n)
// 版本三
class Solution {
private:
void traversal(TreeNode* cur, string path, vector<string>& result) {
path += to_string(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中
if (cur->left == NULL && cur->right == NULL) {
result.push_back(path);
return;
}
if (cur->left) {
path += "->";
traversal(cur->left, path, result); // 左
path.pop_back(); // 回溯 '>'
path.pop_back(); // 回溯 '-'
}
if (cur->right) {
path += "->";
traversal(cur->right, path, result); // 右
path.pop_back(); // 回溯'>'
path.pop_back(); // 回溯 '-'
}
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
string path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}
};迭代(前序遍历)
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
stack<TreeNode*> treeSt;// 保存树的遍历节点
stack<string> pathSt; // 保存遍历路径的节点
vector<string> result; // 保存最终路径集合
if (root == NULL) return result;
treeSt.push(root);
pathSt.push(to_string(root->val));
while (!treeSt.empty()) {
TreeNode* node = treeSt.top(); treeSt.pop(); // 取出节点 中
string path = pathSt.top();pathSt.pop(); // 取出该节点对应的路径
if (node->left == NULL && node->right == NULL) { // 遇到叶子节点
result.push_back(path);
}
if (node->right) { // 右
treeSt.push(node->right);
pathSt.push(path + "->" + to_string(node->right->val));
}
if (node->left) { // 左
treeSt.push(node->left);
pathSt.push(path + "->" + to_string(node->left->val));
}
}
return result;
}
};404. 左叶子之和 - 力扣（LeetCode）
思路:使用迭代法前序遍历二叉树，如果当前节点的右节点非空，直接推入栈，如果当前节点的左节点非空，就在后面再推入一个标记节点(该节点值为特殊值或者改节点为空节点都可以)，如果当前遍历到的节点是标记节点，那么先弹出，然后判断此时在栈顶的节点是否无左右孩子，如果无左右孩子则说明是题目描述的左叶子，否则只弹出标记节点
我的AC代码
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
int sum = 0;
stack<TreeNode*> st;
if(root == nullptr) {
return 0;
}
st.push(root);
while(!st.empty()) {
TreeNode* tmp = st.top();
st.pop();
if(tmp->right) {
st.push(tmp->right);
}
if(tmp->left) {
st.push(tmp->left);
TreeNode* sign = new TreeNode(-9999);
st.push(sign);
}
if(tmp->val == -9999) {
if(!st.top()->left && !st.top()->right) {
sum += st.top()->val;
st.pop();
}
}
}
return sum;
}
};标准答案
递归1
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right== NULL) 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;
}
};递归2
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == NULL) return 0;
int leftValue = 0;
if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {
leftValue = root->left->val;
}
return leftValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
};迭代法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
stack<TreeNode*> st;
if (root == NULL) return 0;
st.push(root);
int result = 0;
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
result += node->left->val;
}
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
return result;
}
};额外题目
100. 相同的树 - 力扣（LeetCode）
我的AC代码
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
bool same(TreeNode* l, TreeNode* r) {
if(l == nullptr && r == nullptr) {
return true;
}
if(l == nullptr && r !=nullptr) {
return false;
}
if(l != nullptr && r ==nullptr) {
return false;
}
if(l->val != r->val) {
return false;
}
return same(l->left, r->left) && same(l->right, r->right);
}
bool isSameTree(TreeNode* p, TreeNode* q) {
return same(p, q);
}
};572. 另一棵树的子树 - 力扣（LeetCode）
我的AC代码
//时间复杂度O(n2),空间复杂度O(n)
class Solution {
public:
bool same(TreeNode* l, TreeNode* r) {
if(!l && !r) {
return true;
}
if(l && !r) {
return false;
}
if(!l && r) {
return false;
}
if(r->val != l->val) {
return false;
}
return same(l->left, r->left) && same(l->right, r->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
stack<TreeNode*> st;
st.push(root);
while(!st.empty()) {
TreeNode* tmp = st.top();
if(same(tmp, subRoot)) {
return true;
}
st.pop();
if(tmp->left) {
st.push(tmp->left);
}
if(tmp->right) {
st.push(tmp->right);
}
}
return false;
}
};
Comments NOTHING