大纲
● 110.平衡二叉树
● 257. 二叉树的所有路径
● 404.左叶子之和
平衡二叉树
题目链接:110.平衡二叉树
分析过程:
本题的解题思路是求最大深度和最短路径元素个数后,判断两者差是否小于1
// 二叉树是否平衡
void minMaxDepth(TreeNode* root, int count, int& min, int& max) {
if (!root) {
if (min > count) min = count;
if (max < count) max = count;
return;
}
count++;
minMaxDepth(root->left, count, min, max);
minMaxDepth(root->right, count, min, max);
count--;
}
bool isBalanceTree(TreeNode* root)
{
int min = INT_MAX;
int max = INT_MIN;
minMaxDepth(root, 0, min, max);
if (max - min > 1) {
return false;
}
return true;
}
二叉树的所有路径
题目链接: 257. 二叉树的所有路径
分析过程:
给定一个二叉树,返回所有从根节点到叶子节点的路径
// 所有的叶子节点
// 叶子节点:左右都为空的节点
// 使用回溯+递归法
// 递归参数:root [路径list] 返回值list
// 结束条件:root左右都为空
void getTreePath(TreeNode* root, vector<TreeNode*>& prePath, vector<string>& ret)
{
// 节点为空结束
if (!root) return;
if (!root->left && !root->right) {
string str;
for (int i = 0; i < prePath.size(); ++i) {
str.append(std::to_string(prePath[i]->val));
str.append("->");
}
str.append(std::to_string(root->val));
ret.push_back(str);
return;
}
prePath.push_back(root);
getTreePath(root->left, prePath, ret);
getTreePath(root->right, prePath, ret);
prePath.pop_back();
}
vector<string> getAllTreePath(TreeNode* root)
{
vector<string> ret;
if (!root) return ret;
vector<TreeNode*> path;
getTreePath(root, path, ret);
return ret;
}
遇到问题:
1 忘记怎么把int 转string
2 忘记vector删除最后元素接口
3 没有想清楚递归结束条件,如果是root空怎么办,未处理
左叶子之和
题目链接:404.左叶子之和
// 左叶子之和
// 需要前一个节点 + 当前节点 如果当前节点的左右节点空 且 pre->left = cur
// 递归结束条件:root空 或者 是叶子节点
// 递归参数:root preNode, sum
void leftNodeSum(TreeNode* root, TreeNode* preNode, int& sum) {
if (!root) return;
// 是叶子节点
if (preNode
&& !root->left
&& !root->right
&& preNode->left == root) {
sum += root->val;
return;
}
preNode = root;
leftNodeSum(root->left, preNode, sum);
leftNodeSum(root->right, preNode, sum);
}
int getLeftNodesSum(TreeNode* root) {
int sum = 0;
TreeNode* preNode = nullptr;
leftNodeSum(root, preNode, sum);
return sum;
}