【算法学习】递归篇
2022/7/24 1:23:56
本文主要是介绍【算法学习】递归篇,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【2022/7/21】814. 二叉树剪枝
问题
知识点回顾
1. 什么是二叉树?
- 本身是有序树
- 树中包含的各个节点的度不能超过 2,即只能是 0、1 或者 2
2. 二叉树的性质
- 第 i 层最多有 2i-1 个结点
- 若二叉树的深度为 K,那么此二叉树最多有 2K-1 个结点
解题思路
用递归实现:
- 临界值:当传入的节点为null时,返回null
- 剪枝:当传入节点的val为0,左节点为null,右节点为null时,进行剪枝处理(返回null
代码:
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 TreeNode pruneTree(TreeNode root) { if(root==null){ return null; } root.left=pruneTree(root.left); root.right= pruneTree(root.right); if(root.val==0 && root.left==null && root.right==null){ return null; } return root; } }
提交记录
【2022/7/23] 2. 两数相加
问题
解题思路
用递归实现:
- 设置一个变量i存储进位(取值为1或0),直接将相加后的值存储到l1中
- 临界值:下一位都是空以及进位为零时退出
代码
class Solution { static int i=0; public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 临界值 if(l1==null && l2==null && Solution.i==0){ return l1; } // 相加,相加后的值存储到l1中,并且改变进位值 if(l1.val+l2.val+Solution.i>9){ l1.val=l1.val+l2.val-10+Solution.i; Solution.i=1; }else{ l1.val=l1.val+l2.val+Solution.i; Solution.i=0; } // 除了->(两个节点的next都为null,并且进位为零)这种情况外,将节点的next后面补0(避免节点的next为null但是还有进位的情况 if(!(l1.next==null && l2.next==null && Solution.i==0)){ if(l1.next==null){ l1.next=new ListNode(0,null); } if(l2.next==null){ l2.next=new ListNode(0,null); } } addTwoNumbers(l1.next,l2.next); return l1; } }
提交结果
这篇关于【算法学习】递归篇的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署