【每日刷题】Day64
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. LCP 67. 装饰树 - 力扣（LeetCode）
3. 1315. 祖父节点值为偶数的节点和 - 力扣（LeetCode）
3. LCP 44. 开幕式焰火 - 力扣（LeetCode）
1. LCP 67. 装饰树 - 力扣（LeetCode）
//100％思路：类似链表插入结点的思路。深度优先遍历二叉树，当为空或遇到叶子结点时返回。判断当前非叶子结点左、右孩子是否为空，创建一个存储的值为-1的新结点，将其类似链表插入结点的形式插入到父结点与左、右孩子结点之间。
typedef struct TreeNode TN;
//判断是否为叶子结点
bool IsLeafNode(TN* root)
{
return !root->left&&!root->right;
}
void _expandBinaryTree(TN* root)
{
//遍历到空或叶子结点直接返回，不需要插入装饰
if(!root||IsLeafNode(root))
return;
if(root->left&&root->val!=-1)//左孩子与其父亲节点间插入装饰(注意这里遍历时需要跳过插入的装饰)
{
TN* node = (TN*)malloc(sizeof(TN));
node->val = -1;
node->left = root->left;
node->right = NULL;
root->left = node;
}
if(root->right&&root->val!=-1)//同上
{
TN* node = (TN*)malloc(sizeof(TN));
node->val = -1;
node->right = root->right;
node->left = NULL;
root->right = node;
}
//先序遍历
_expandBinaryTree(root->left);
_expandBinaryTree(root->right);
}
struct TreeNode* expandBinaryTree(struct TreeNode* root)
{
_expandBinaryTree(root);
return root;
}
3. 1315. 祖父节点值为偶数的节点和 - 力扣（LeetCode）
//思路：深度优先遍历。遍历二叉树，遇到值为偶数的结点时，以该结点为根结点看作一棵树，算出其第2层的结点值的和返回。
typedef struct TreeNode TN;
//计算第k层结点值的和int BinaryTreeKNum(TN* root,int k)
{
if(!root)
return 0;
if(k==0)
return root->val;
return BinaryTreeKNum(root->left,k-1)+BinaryTreeKNum(root->right,k-1);
}
void _sumEvenGrandparent(TN* root,int* ans)
{
if(!root)
return;
if((root->val)%2==0)//遇到值为偶数的结点，算出其孙子结点值的和
(*ans)+=BinaryTreeKNum(root,2);
//深度优先遍历
_sumEvenGrandparent(root->left,ans);
_sumEvenGrandparent(root->right,ans);
}
int sumEvenGrandparent(struct TreeNode* root)
{
int ans = 0;
_sumEvenGrandparent(root,&ans);
return ans;
}
3. LCP 44. 开幕式焰火 - 力扣（LeetCode）
//思路：深度优先遍历+哈希表。遍历二叉树，以二叉树结点的值为key，将哈希表key位置的val该为1。遍历哈希表，计算1的数量。
typedef struct TreeNode TN;
void _numColor(TN* root,int* hash)
{
if(!root)
return;
hash[root->val] = 1;//以root->val为key，val为1
_numColor(root->left,hash);
_numColor(root->right,hash);
}
int numColor(struct TreeNode* root)
{
int hash[1001] = {0};
int ans = 0;
_numColor(root,hash);
for(int i = 0;i<1001;i++)
{
if(hash[i])//计算1的数量
ans++;
}
return ans;
}
