【每日刷题】Day47

🥕个人主页：开敲🍉

🔥所属专栏：每日刷题🍍

🌼文章目录🌼

1. 112. 路径总和 - 力扣（LeetCode）

2. 2404. 出现最频繁的偶数元素 - 力扣（LeetCode）

3. 145. 二叉树的后序遍历 - 力扣（LeetCode）

1. 112. 路径总和 - 力扣（LeetCode）

//思路：遍历二叉树。用一个变量将二叉树上一个结点的值相加传给下一个递归，继续加上下一个结点的值，直到加到叶子结点判断是否等于目标值，相等则返回true，否则返回false。如果遇到空直接返回false。

typedef struct TreeNode BT;

//判断是否为叶子结点

bool IsLeafNode(BT* node)

{

    return !node->left&&!node->right;

}

 

//前序遍历

bool PreambleTraverse(BT* node,int targetSum,int sum)

{

    if(node==NULL)

    {

        return false;

    }

    if(IsLeafNode(node))//遇到叶子结点判断值是否等于目标值

    {

        if((sum+node->val)!=targetSum)//不等于返回false

        {

            return false;

        }

        return true;

    }

    return PreambleTraverse(node->left,targetSum,sum+node->val)||PreambleTraverse(node->right,targetSum,sum+node->val);//只要左右子树中有一条路径满足即可

}

 

bool hasPathSum(struct TreeNode* root, int targetSum)

{

    if(root==NULL)

    {

        return false;

    }

    int sum = 0;

    return PreambleTraverse(root,targetSum,sum);

}

2. 2404. 出现最频繁的偶数元素 - 力扣（LeetCode）

//哈希表多次查询。将整数数组中的元素的值作为哈希表的下标，每次该下标处的值+1。遍历哈希表找到出现次数最多的偶数的出现次数。再次遍历哈希表，找到最小的出现次数最多的偶数返回。

int mostFrequentEven(int* nums, int numsSize)

{

    int hash[100001] = {0};

    for(int i = 0;i<numsSize;i++)

    {

        hash[nums[i]]+=1;

    }

    int max = 0;

    for(int i = 0;i<100001;i++)

    {

        if(i%2==0)

        {

            max = max>hash[i]?max:hash[i];

        }

    }

    int ans = -1;

    if(max==0)

    {

        return ans;

    }

    for(int i = 0;i<100001;i++)

    {

        if(i%2==0&&hash[i]==max)

        {

            ans = i;

            break;

        }

    }

    return ans;

}

3. 145. 二叉树的后序遍历 - 力扣（LeetCode）

//思路：后序遍历：对于每个结点，都满足：左子树、右子树、根 的遍历方式。

void BackTraverse(struct TreeNode* root,int* arr,int* size)

{

    if(root==NULL)

    {

        return;

    }

    BackTraverse(root->left,arr,size);

    BackTraverse(root->right,arr,size);

    arr[(*size)++] = root->val;

}

int* postorderTraversal(struct TreeNode* root, int* returnSize)

{

    int* ans = (int*)malloc(sizeof(int)*101);

    int size = 0;

    BackTraverse(root,ans,&size);

    *returnSize = size;

    return ans;

}