二叉树中和为某一值的路径(push,pop;add,removeLast;offer,pollLast ) ( 模拟添加完结点后,立马更新target并且判断target是否为0)Leetcode51
2022/2/20 23:56:41
本文主要是介绍二叉树中和为某一值的路径(push,pop;add,removeLast;offer,pollLast ) ( 模拟添加完结点后,立马更新target并且判断target是否为0)Leetcode51,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
递归是线程安全的, 最开始的一条路不返回的话,下一条路永远不会开始
但是在只有一个工作数组的情况下,一条路结束以后要创建数组的副本,来防止下一条路上的操作对前一条路的结果造成污染
class Solution { List<List<Integer>> res; public List<List<Integer>> pathSum(TreeNode root, int target) { // if(root == null){ // 不用加这一个判断,因为root为空的话,res里面还是空List,正好 // return null; // } // (LinkedList)小的 可以冒充 (List)大的 LinkedList<Integer> tem = new LinkedList<>();// LinkedList可以当做List对象放进去,递归的做法只能在递归函数外面创建容器,然后结合容器复制的技术来防污染 res = new LinkedList<>(); // tem 保存一条满足条件的路径, res保存所有的tem dfs(root,target,tem); return res; } public void dfs(TreeNode root , int k , LinkedList<Integer> tem){ if(root == null){ return; } tem.add(root.val); // 必须在 判断 k == 0 之前,进行 k -= root.val; 并将 root.val 加进tem; k -= root.val; // 否则, 就会少了 当前节点val值的贡献 // 一加进去root.val 接下来就进行判断 // 加进来这一轮结点的val值了,现在可以判断了 if(root.left == null && root.right == null){//开始判断 if(k==0){ // 递归是线程安全的, 最开始的一条路不返回的话,下一条路永远不会开始 //这里要创建一个新的List集合,将tem复制一份放进去 //这样是为了避免分支污染,也就是后续对tem的操作,影响了前面的路径 //虽然递归不用考虑多线程的影响(它是一条路走到黑的),但是由于递归只能在递归函数之外创建容器,所以我保存多条路径的时候都是用的用一个容器,所以需要创建副本来保证安全,如果不用递归的方法,用迭代的话,我就可以在循环里面new一个新容器,将其保存起来后,这个循环结束,此容器就会自动销毁 res.add(new LinkedList<>(tem)); //直接res.add(tem); 这样是错的 } } dfs(root.left,k,tem); dfs(root.right,k,tem); tem.removeLast(); // removelast 和 polllast都是从list 的 end移除并返回这个元素 :在队尾操作 // add 和 offer 是在 List 的 end 添加元素 :在队尾操作 // push 和 pop 是在 List 的 start 添加 和 移除 元素 :在队首操作 } }
这篇关于二叉树中和为某一值的路径(push,pop;add,removeLast;offer,pollLast ) ( 模拟添加完结点后,立马更新target并且判断target是否为0)Leetcode51的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升