110. 平衡二叉树
题目链接：
https://leetcode.cn/problems/balanced-binary-tree/
算法思想：
平衡二叉树，左右子树的高度差不超过1.要获取到当前节点的高度，获取计算得到左右子树的高度，因为使用后续遍历。
1.明确返回值类型和参数：
2.明确递归终止条件：当root==NULL，递归终止
3.明确单次的逻辑：计算左右子树的高度，获取高度差判断
代码：
class Solution {
public:
int getheight(TreeNode* node)
{
if(node==NULL)
{
return 0;
}
int left = getheight(node->left);
if(left==-1)
return -1;
int right = getheight(node->right);
if(right==-1)
return -1;
if(abs(left-right)>1)
return -1;
return max(left, right) + 1;
}
bool isBalanced(TreeNode* root) {
int res = getheight(root);
if(res==-1)
return false;
else
return true;
}
};
257. 二叉树的所有路径
题目链接：
https://leetcode.cn/problems/binary-tree-paths/
算法思想：
确定遍历方式：前序遍历。
注意返回条件。
代码：
class Solution {
public:
void getpath(TreeNode* root, vector<int>&path, vector<vector<int>> & result)
{
path.push_back(root->val);
if(root->left==NULL&&root->right==NULL)
{
vector<int> res;
for(int i=0;i<path.size();i++)
{
res.push_back(path[i]);
}
result.push_back(res);
}
if(root->left!=NULL)
{
getpath(root->left, path, result);
path.pop_back();
}
if(root->right!=NULL)
{
getpath(root->right, path, result);
path.pop_back();
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<vector<int>> result;
vector<int> path;
getpath(root, path, result);
vector<string> final;
for(int i=0;i<result.size();i++)
{
string s="";
for(int j=0;j<result[i].size()-1;j++)
{
s = s + to_string(result[i][j]) + "->" ;
}
s = s+to_string(result[i][result[i].size()-1]);
final.push_back(s);
}
return final;
}
};
404. 左叶子之和
题目链接：
https://leetcode.cn/problems/sum-of-left-leaves/
算法思想：
确定遍历顺序：因为要求和，需要获取到左右子树的值，因此是后续遍历。
确定递归终止条件：root==NULL的时候，或者遍历到左叶子节点的时候。
代码：
class Solution {
public:
int sum(TreeNode* node)
{
if(node==NULL)
return 0;
int left = sum(node->left);
if(node!=NULL&&node->left!=NULL&&node->left->left==NULL&&node->left->right==NULL)
left = node->left->val;
int right = sum(node->right);
return left+right;
}
int sumOfLeftLeaves(TreeNode* root) {
return sum(root);
}
};
