[TOC]
第一题
解法一[递归法]
-
空间复杂度O(n)
-
空间复杂度O(log(n))
class Solution {
public:
int getHeight(TreeNode* cur){
if (cur == NULL) return 0;
int left_height = getHeight(cur->left);
// 在左子树不平衡的时候提前返回
if (left_height == -1) return -1;
int right_height = getHeight(cur->right);
// 在右子树不平衡的时候提前返回
if (right_height == -1) return -1;
return abs(left_height - right_height) > 1 ? -1 : 1 + max(left_height, right_height);
}
bool isBalanced(TreeNode* root) {
return getHeight(root) == -1 ? false : true;;
}
};
解法二[迭代法]
- 空间复杂度O(n)
- 空间复杂度O(n)
class Solution {
private:
int getDepth(TreeNode* cur){
stack<TreeNode*> node_stack;
if (cur !=NULL) node_stack.push(cur);
int height = 0;
int depth = 0;
while(!node_stack.empty()){
TreeNode* tmp = node_stack.top();
if (tmp != NULL){
node_stack.pop();
node_stack.push(tmp);
node_stack.push(NULL);
if (tmp->right) node_stack.push(tmp->right);
if (tmp->left) node_stack.push(tmp->left);
depth++;
}
else{
node_stack.pop();
tmp = node_stack.top();
node_stack.pop();
depth--;
}
height = height > depth ? height : depth;
}
return height;
}
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;
}
};
总结
- 对于高度与深度的概念需要区分，二叉树的高度指的是从下往上，也就是当前结点到根结点的结点个数。二叉树的深度是从上往下，也就是根结点到当前结点的结点个数。
- 对于求二叉树的高度，一般使用后序遍历，求二叉树的深度一般使用前序遍历。
- 对于迭代法，本题的两个后序遍历的应用，一个用于求子树的高度，一个用于遍历结点。
第二题
解法一[递归法]
class Solution {
public:
void subTreepath(TreeNode* cur, vector<int>& path, vector<string>& result){
path.push_back(cur->val); // 中
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);
}
if (cur->left){
subTreepath(cur->left, path, result);
path.pop_back(); // 回溯
}
if (cur->right){
subTreepath(cur->right, path, result);
path.pop_back(); // 回溯
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
if (root == NULL) return result;
subTreepath(root, path, result);
return result;
}
};
解法二[迭代法]
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
stack<TreeNode*> node_stack;
stack<string> spath;
if (root == NULL) return result;
node_stack.push(root);
spath.push(to_string(root->val));
while(!node_stack.empty()){
TreeNode* cur = node_stack.top();
node_stack.pop();
string path = spath.top();
spath.pop();
if (cur->left != NULL) {
node_stack.push(cur->left);
spath.push(path + "->" + to_string(cur->left->val));
}
if (cur->right != NULL) {
node_stack.push(cur->right);
spath.push(path + "->" + to_string(cur->right->val));
}
if (cur->left == NULL && cur->right == NULL) {
result.push_back(path);
}
}
return result;
}
};
总结
- 感觉对于递归和迭代还是没有学习的很透彻，已经连续几道题没有写出来了，这道题主要没有想到需要一个vector来记录当前根结点到目前结点的结点。
- 对于迭代法，本题使用一个栈用来遍历，一个栈用来记录当前路径。
第三题
解法一[后序遍历递归法]
- 时间复杂度O(n)
- 空间复杂度O(n)
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == 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;
}
};
解法二[前序遍历迭代法]
- 时间复杂度O(n)
- 空间复杂度O(n)
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
int result = 0;
stack<TreeNode*> node_stack;
node_stack.push(root);
while (!node_stack.empty()){
TreeNode* cur = node_stack.top();
//std::cout << cur->val << std::endl;
node_stack.pop();
if (cur->left != NULL) {
node_stack.push(cur->left);
if (cur->left->right == NULL && cur->left->left == NULL){
result += cur->left->val;
}
}
if (cur->right != NULL) node_stack.push(cur->right);
}
return result;
}
};
解法三[中序遍历迭代法]
- 时间复杂度O(n)
- 空间复杂度O(n)
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
int result = 0;
stack<TreeNode*> node_stack;
TreeNode* cur = root;
while (cur != NULL || !node_stack.empty()){
if (cur != NULL){
node_stack.push(cur);
cur = cur->left;
}
else{
cur = node_stack.top();
if (cur->left != NULL && cur->left->left == NULL && cur->left->right == NULL){
result += cur->left->val;
}
node_stack.pop();
cur = cur->right;
}
}
return result;
}
};
总结
- 这道题算是比较简单，迭代法应该遍历即可，递归法需要后序遍历。
- 可以用来复习集中遍历方法。
总结
感觉自己对于遍历的应用不是很熟悉，还是需要持续的刷题，前面断了一段时间，感觉就没有想法了。
