网站建设与管理教学视频,西安网站品牌建设,少女心仙气手工,网站策划方法文章目录 前言1. 两两交换链表中的节点1.1 题目要求1.2 做题思路1.3 代码实现 2. Pow(X,N)2.1 题目要求2.2 做题思路2.3 代码实现 3. 计算布尔二叉树的值3.1 题目要求3.2 做题思路3.3 代码实现 4. 求根节点到叶结点数字之和4.1 题目要求4.2 做题思路4.3 代码实现 前言
前面为大… 文章目录 前言1. 两两交换链表中的节点1.1 题目要求1.2 做题思路1.3 代码实现 2. Pow(X,N)2.1 题目要求2.2 做题思路2.3 代码实现 3. 计算布尔二叉树的值3.1 题目要求3.2 做题思路3.3 代码实现 4. 求根节点到叶结点数字之和4.1 题目要求4.2 做题思路4.3 代码实现 前言
前面为大家介绍了关于递归的知识以及使用递归解决了几个问题那么这篇文章将带大家巩固一下关于递归的知识。
1. 两两交换链表中的节点
https://leetcode.cn/problems/swap-nodes-in-pairs/description/
1.1 题目要求
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
示例 1
输入head [1,2,3,4]
输出[2,1,4,3]示例 2
输入head []
输出[]示例 3
输入head [1]
输出[1]提示
链表中节点的数目在范围 [0, 100] 内
0 Node.val 100/*** Definition for singly-linked list.* 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 {public ListNode swapPairs(ListNode head) {}
}1.2 做题思路
这道题目其实可以使用非递归的方式来实现但是我们可以使用递归的方式来加深一下递归的学习。
这个题目不复杂比较简单我们可以将 head 和 head.next 看成一部分另外的节点看成另一部分开始我们直接将后面部分的节点交给函数处理相信它一定可以帮助我们完成两两节点的交换当后面部分的节点交换完成之后我们再交换 head 和 head.next 节点然后再将这两个部分连接起来。 这是一种思路我们也可以先交换前面部分然后再交换后面部分。 上面两种思路其实都差不多的只是先交换还是后交换的区别。
1.3 代码实现
/*** Definition for singly-linked list.* 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 {public ListNode swapPairs(ListNode head) {if (head null || head.next null) return head;ListNode l1 swapPairs(head.next.next);ListNode ret head.next;head.next.next head;head.next l1;return ret;}
}/*** Definition for singly-linked list.* 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 {public ListNode swapPairs(ListNode head) {if (head null || head.next null) return head;ListNode curNext head.next.next;ListNode ret head.next;head.next.next head;head.next swapPairs(curNext);return ret;}
}2. Pow(X,N)
https://leetcode.cn/problems/powx-n/
2.1 题目要求
实现 pow(x, n) 即计算 x 的整数 n 次幂函数即xn 。
示例 1
输入x 2.00000, n 10
输出1024.00000示例 2
输入x 2.10000, n 3
输出9.26100示例 3
输入x 2.00000, n -2
输出0.25000
解释2-2 1/22 1/4 0.25提示
-100.0 x 100.0
-231 n 231-1
n 是一个整数
要么 x 不为零要么 n 0 。
-104 xn 104class Solution {public double myPow(double x, int n) {}
}2.2 做题思路
其实这道题也叫做快速幂为什么叫做快速幂呢给大家举个例子假设我们要求2^8普通的做法就是2x2x2x2x2x2x2x2但是呢2 ^ 8可以写成 2 ^ 4 x 2 ^ 4而 2 ^ 4 又可以写成 2 ^ 2 x 2 ^ 22 ^ 2可以写成 2 x 22 可以写成 1 x 2。也就是说 2 ^ n 可以写成 2 ^ (n / 2) x 2 ^ (n / 2)我们每次只需要计算 2 ^ (n / 2) 的值及就可以了通过这种快速幂的方法就可以大大节省计算的时间。
当幂为偶数的话就可以每次求 x 的 n / 2 次幂但是如果幂数为奇数该怎么办呢这也不复杂当幂数为奇数的时候我们只需要在 n / 2 次幂 x n / 2 次幂后面在乘上一个 x 就可以了。举个例子2 ^ 5就可以写成 2 ^ 2 x 2 ^ 2 x 2。
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 题目要求
给你一棵 完整二叉树 的根这棵树有以下特征
叶子节点 要么值为 0 要么值为 1 其中 0 表示 False 1 表示 True 。 非叶子节点 要么值为 2 要么值为 3 其中 2 表示逻辑或 OR 3 表示逻辑与 AND
计算 一个节点的值方式如下
如果节点是个叶子节点那么节点的 值 为它本身即 True 或者 False 。 否则计算 两个孩子的节点值然后将该节点的运算符对两个孩子值进行 运算 。 返回根节点 root 的布尔运算值。
完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。
叶子节点 是没有孩子的节点。
示例 1
输入root [2,1,3,null,null,0,1]
输出true
解释上图展示了计算过程。
AND 与运算节点的值为 False AND True False 。
OR 运算节点的值为 True OR False True 。
根节点的值为 True 所以我们返回 true 。示例 2
输入root [0]
输出false
解释根节点是叶子节点且值为 false所以我们返回 false 。提示
树中节点数目在 [1, 1000] 之间。
0 Node.val 3
每个节点的孩子数为 0 或 2 。
叶子节点的值为 0 或 1 。
非叶子节点的值为 2 或 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.2 做题思路
这道题目的意思就是如果遇到的节点是一个叶子节点的话如果当前节点的值为0的话就返回False为1的话就返回True如果当前节点不是叶子节点的话就需要根据这个节点的父亲节点的值与这个节点的兄弟节点进行操作如果父亲节点是2的话就进行 | 操作3就进行 操作。
一般遇到二叉树就会想到递归这道题也不例外。我们先将根节点的左树交给函数让函数帮助我们进行布尔值的计算然后再将根节点的右树交给函数进行布尔值的运算最后将左右子树的值与根节点表示的值进行 | 或者 运算。 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时返回trueif (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 树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字
例如从根节点到叶节点的路径 1 - 2 - 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1
输入root [1,2,3]
输出25
解释
从根到叶子节点路径 1-2 代表数字 12
从根到叶子节点路径 1-3 代表数字 13
因此数字总和 12 13 25示例 2 输入root [4,9,0,5,1]
输出1026
解释
从根到叶子节点路径 4-9-5 代表数字 495
从根到叶子节点路径 4-9-1 代表数字 491
从根到叶子节点路径 4-0 代表数字 40
因此数字总和 495 491 40 1026提示
树中节点的数目在范围 [1, 1000] 内
0 Node.val 9
树的深度不超过 10/*** 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.2 做题思路
这道题目也不难只要能理解二叉树的的前序遍历就可以了这道题目其实就是二叉树的前序遍历。我们先将根节点的左子树交给函数得到左子树上从根节点到各个叶子节点路径上的数字之和然后将根节点的右子树上的从根节点到各个叶子节点路径上的数字之和然后返回左子树和右子树返回值的和。
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;}
}
