【每日刷题】Day111
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. LCR 047. 二叉树剪枝 - 力扣（LeetCode）
2. LCR 049. 求根节点到叶节点数字之和 - 力扣（LeetCode）
3. 257. 二叉树的所有路径 - 力扣（LeetCode）
1. LCR 047. 二叉树剪枝 - 力扣（LeetCode）
//思路：深度优先。
//深度优先遍历二叉树，遇到空返回除0以外的任意值即可；遇到叶子节点返回叶子节点的值。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool IsLeafNode(TreeNode* root)
{
return !root->left&&!root->right;
}
int _pruneTree(TreeNode* root)
{
//遍历到空，返回除0外的任意值
if(!root) return 1;
//遇到叶子节点，返回叶子结点的值
if(IsLeafNode(root)) return root->val;
//获取左节点的值
int left = _pruneTree(root->left);
//如果左节点是叶子节点且值为0，则裁剪掉左节点
if(!left&&IsLeafNode(root->left)) root->left = nullptr;
//同上
int right = _pruneTree(root->right);
if(!right&&IsLeafNode(root->right)) root->right = nullptr;
//返回当前节点值
return root->val;
}
TreeNode* pruneTree(TreeNode* root)
{
_pruneTree(root);
//处理根节点是叶子节点且值为0的情况
if(!root->val&&IsLeafNode(root)) return nullptr;
return root;
}
};
2. LCR 049. 求根节点到叶节点数字之和 - 力扣（LeetCode）
//思路：深度优先+栈。
//深度优先遍历二叉树，每遍历到一个节点记录节点的val，使用string记录为字符串，方便后续获得路径所组成的数字。
//遍历到空时什么也不做，直接return
//当左右子节点都遍历完后，当前节点路径结束，pop掉当前节点
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool IsLeafNode(TreeNode* root)
{
return !root->left&&!root->right;
}
void _sumNumbers(TreeNode* root,int& ans,string& stack)
{
if(!root) return;
stack.push_back(root->val+'0');
if(IsLeafNode(root))
{
ans+=stoi(stack);
stack.pop_back();
return;
}
_sumNumbers(root->left,ans,stack);
_sumNumbers(root->right,ans,stack);
stack.pop_back();
}
int sumNumbers(TreeNode* root)
{
int ans = 0;
string stack;
_sumNumbers(root,ans,stack);
return ans;
}
};
3. 257. 二叉树的所有路径 - 力扣（LeetCode）
//思路：深度优先。
//利用每次递归都会创建新的函数栈帧的特性，我们可以做到类似于栈的功能。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
//判断是否为叶子节点
bool IsLeafNode(TreeNode* root)
{
return !root->left&&!root->right;
}
void _binaryTreePaths(TreeNode* root,vector<string>& ans,string tmp)
{
//遇到空直接返回
if(!root) return;
//不为空则插入字符串
tmp+=to_string(root->val);
tmp+="->";
if(IsLeafNode(root))
{
//叶子节点后会多一个"->"，手动删除
tmp.pop_back();
tmp.pop_back();
ans.push_back(tmp);
return;
}
_binaryTreePaths(root->left,ans,tmp);
_binaryTreePaths(root->right,ans,tmp);
}
vector<string> binaryTreePaths(TreeNode* root)
{
vector<string> ans;
string tmp;
_binaryTreePaths(root,ans,tmp);
return ans;
}
};
