# 【算法系列篇】递归、搜索和回溯（二）

## 1. 两两交换链表中的节点

https://leetcode.cn/problems/swap-nodes-in-pairs/description/

### 1.1 题目要求

输入：head = [1,2,3,4]

输入：head = []

输入：head = [1]

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
}
}


### 1.3 代码实现

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
return ret;
}
}


/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
return ret;
}
}


## 2. Pow(X,N)

https://leetcode.cn/problems/powx-n/

### 2.1 题目要求

输入：x = 2.00000, n = 10

输入：x = 2.10000, n = 3

输入：x = 2.00000, n = -2

-100.0 < x < 100.0
-231 <= n <= 231-1
n 是一个整数

-104 <= xn <= 104

class Solution {
public double myPow(double x, int n) {
}
}


### 2.3 代码实现

class Solution {
public double myPow(double x, int n) {
//处理幂数的正负问题
if (n < 0) return 1.0 / quickPow(x, n);
else return quickPow(x, n);
}
private double quickPow(double x, int n) {
if (n == 0) return 1.0;
double t = quickPow(x, n / 2);
//处理幂数的奇偶问题
return n % 2 == 0 ? t * t : t * t * x;
}
}


## 3. 计算布尔二叉树的值

https://leetcode.cn/problems/evaluate-boolean-binary-tree/

### 3.1 题目要求

输入：root = [2,1,3,null,null,0,1]

AND 与运算节点的值为 False AND True = False 。
OR 运算节点的值为 True OR False = True 。



输入：root = [0]

树中节点数目在 [1, 1000] 之间。
0 <= Node.val <= 3


/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public boolean evaluateTree(TreeNode root) {
}
}


### 3.3 代码实现

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public boolean evaluateTree(TreeNode root) {
//当root为null时返回true
if (root == null) return true;
//遇到叶子节点根据节点的值返回
if (root.left == null && root.right == null) {
if (root.val == 0) return false;
else return true;
}
boolean l = evaluateTree(root.left);
boolean r = evaluateTree(root.right);
if (root.val == 2) return l | r;
else return l & r;
}
}


## 4. 求根节点到叶结点数字之和

https://leetcode.cn/problems/sum-root-to-leaf-numbers/

### 4.1 题目要求

输入：root = [1,2,3]



输入：root = [4,9,0,5,1]



树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public int sumNumbers(TreeNode root) {
}
}


### 4.3 代码实现

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
//n用来记录当前路径上该节点之前的各个节点的和
private int dfs(TreeNode root, int n) {
if (root == null) return 0;
//遇到一个节点就将当前节点的值加在n上
n = n * 10 + root.val;
//遇到叶子节点就说明当前节点的值计算完成，就返回路径上所以数字和
if (root.left == null && root.right == null) return n;
//分别计算根节点左右子树上根节点到叶子节点路径上数字和
int l = dfs(root.left, n);
int r = dfs(root.right, n);
//返回左子树和右子树所有路径上数字和
return l + r;
}
}


|
7天前
|

【5月更文挑战第11天】本文介绍了图搜索算法的基础知识，包括深度优先搜索（DFS）、广度优先搜索（BFS）和启发式搜索（如A*算法）。讨论了图搜索中的常见问题、易错点及避免方法，并提供了BFS和A*的Python代码示例。文章强调了正确标记节点、边界条件检查、测试与调试以及选择合适搜索策略的重要性。最后，提到了图搜索在路径规划、游戏AI和网络路由等领域的应用，并概述了性能优化策略。
15 3
|
7天前
|

16 1
|
6天前
|

7 1
|
6天前
|

11 0
|
6天前
|

9 1
|
6天前
|

7 1
|
6天前
|

【AI 初识】人工智能中使用了哪些不同的搜索算法？
【5月更文挑战第2天】【AI 初识】人工智能中使用了哪些不同的搜索算法？
50 5
|
6天前
|

11 2
|
7天前
|

8 0
|
6天前
|

Python中基于网格搜索算法优化的深度学习模型分析糖尿病数据
Python中基于网格搜索算法优化的深度学习模型分析糖尿病数据
23 0