【每日刷题】Day110
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 24. 两两交换链表中的节点 - 力扣（LeetCode）
2. 50. Pow(x, n) - 力扣（LeetCode）
3. 2331. 计算布尔二叉树的值 - 力扣（LeetCode）
1. 24. 两两交换链表中的节点 - 力扣（LeetCode）
//思路：递归。
//看图理解：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head)
{
//当head走到空时，返回head（节点个数为偶数的情况）；当head->next走到空时，返回head（节点个数为奇数的情况）
if(!head||!head->next) return head;
//使用一个临时指针指向haed->next
ListNode* tmp = head->next;
//head->next指向下一次递归返回的结果
head->next = swapPairs(head->next->next);
//实现交换
tmp->next = head;
return tmp;
}
};
2. 50. Pow(x, n) - 力扣（LeetCode）
//思路：快速幂+递归。快速幂是什么？
//当我们有了上述思路后，就可以用递归来实现快速幂。
//但是还有一些细节：
//至此，我们的递归思路就出来了
//同时还有一些细节需要处理，如果n为负数时，我们按照正数幂的方法是不可能算出结果的。不过我们同样可以按照正数幂的方法来算，只不过结果需要改变：
//只需要让1除上结果返回即可
class Solution {
public:
double _mypow(double x,int n)
{
//当幂次分割到0时，就没法再分了，返回1（任何数的0次幂都是1）
if(!n) return 1.0;
//获取当前幂次的一半
double y = _mypow(x,n/2);
//判断当前幂次是奇数还是偶数，如果是奇数，则当前幂次需要额外乘上一个x才能凑出
return n%2?y*y*x:y*y;
}
double myPow(double x, int n)
{
//这里用long long类型的变量接收n也是细节处理。
//当测试用例所给的n是-2^31时，如果我们直接将其转为正数，int类型是没法接收的
long long N = n;
//根据n的值来改变结果
return n>=0?_mypow(x,N):1.0/_mypow(x,-N);
}
};
3. 2331. 计算布尔二叉树的值 - 力扣（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 _evaluateTree(TreeNode* root)
{
//遇到空返回0
if(!root) return 0;
//遇到叶子节点返回叶子节点的值
if(IsLeafNode(root)) return root->val;
//获取当前非叶子节点左子节点值
int left_val = _evaluateTree(root->left);
//获取当前非叶子节点左子节点值
int right_val = _evaluateTree(root->right);
//运算
if(root->val==2) return left_val | right_val;
return left_val & right_val;
}
bool evaluateTree(TreeNode* root)
{
return _evaluateTree(root);
}
};