class Solution {
public:
int getHeight(TreeNode* node)
{
if(node == nullptr)
return 0;
//左子树高度和右子树高度分别计算
int leftHeight = getHeight(node -> left);
int rightHeight = getHeight(node -> right);
// 只要有一边子树返回-1，则证明该子树已经不平衡，向上返回结果
if(leftHeight == -1 || rightHeight == -1)
return -1;
//如果到目前为止子树平衡，比较该层是否平衡
if(abs(leftHeight - rightHeight) > 1)
return -1;
else
// 返回本层树高
return 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
int res = getHeight(root);
if(res == -1)
return false;
else
return true;
}
};
class Solution {
public:
// 回溯法，把递归的过程表示出来了
void traversal(TreeNode* node, vector<int>& vec, vector<string>& path)
{
// 由于判定递归结束条件变为叶子结点结束，因此叶子结点需要考虑到，先来放入结点
vec.push_back(node->val);
// 左节点和右节点均为空， 则表明该节点为叶子结点
if(node -> left == nullptr && node -> right == nullptr)
{
// 字符串拼接逻辑，注意int->string 函数是 to_string()函数
string sPath = "";
for(int i = 0; i<vec.size()-1; i++)
{
sPath += to_string(vec[i]);
sPath += "->";
}
sPath += to_string(vec[vec.size()-1]);
// 到叶子节点了，该干活了
path.push_back(sPath);
}
// 此处判断不为空才调用函数
if(node -> left)
{
// 左边子树遍历
traversal(node -> left, vec, path);
// 回溯的表现，类似于栈后入先出，pop_back()
vec.pop_back();
}
if(node -> right)
{
traversal(node -> right, vec, path);
vec.pop_back();
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<int> vec;
vector<string> path;
// 此处判断根节点自己为空的情况
if(root == nullptr)
return path;
traversal(root, vec, path);
return path;
}
};
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr)
return 0;
// 叶子结点
if(root->left == nullptr && root->right == 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;
}
};
今天的题目还是比较绕的，需要再回顾掌握
