leetcode刷题 | 关于二叉树的题型总结2

简介: 关于二叉树的题型总结2

leetcode刷题 | 关于二叉树的题型总结2

题目链接

129. 求根节点到叶节点数字之和 - 力扣(LeetCode)

437. 路径总和 III - 力扣(LeetCode)

124. 二叉树中的最大路径和 - 力扣(LeetCode)

求根节点到叶节点数字之和

三种解法

第一种带有返回值的dfs,返回值为某一路径的值

classSolution {

   

   publicintsumNumbers(TreeNoderoot) {

       returndfs(root,0);

   }

   publicintdfs(TreeNoderoot,intsum){

       // sum存储的是每一条路径的和

       if(root==null) return0;

       sum=sum*10+root.val;

       if(root.left==null&&root.right==null) returnsum;//返会这条路径的值

       elsereturndfs(root.left,sum)+dfs(root.right,sum); //将左右节点的路径加和

   }

}

第二种不带返回值的递归+回溯

classSolution {

   intsum=0,num=0;

   publicintsumNumbers(TreeNoderoot) {

       dfs(root);

       returnsum;

   }

   publicvoiddfs(TreeNoderoot){

       if(root==null) return;

       num=num*10+root.val;//一直没有到叶子路径

       if(root.left==null&&root.right==null)

           sum+=num; //叶子节点,将这一路径的值加和

       dfs(root.left);

       dfs(root.right);

       num= (num-root.val)/10;

       

   }

}

第三种广度优先搜索,定义两个栈,一个存储节点一个存储节点值

classSolution {

   publicintsumNumbers(TreeNoderoot) {

       Deque<TreeNode>deq1=newArrayDeque();

       Deque<Integer>deq2=newArrayDeque();

       deq1.add(root);

       deq2.add(root.val);

       intsum=0;

       while(!deq1.isEmpty()){

           TreeNodenode=deq1.poll();

           intnum=deq2.poll();

           if(node.left==null&&node.right==null){

               sum+=num;

           }

           if(node.left!=null){

               deq1.add(node.left);

               deq2.add(num*10+node.left.val);

           }

           if(node.right!=null){

               deq1.add(node.right);

               deq2.add(num*10+node.right.val);

           }

       }

       returnsum;

   }

}

路径总和 III

classSolution {

   

   publicintpathSum(TreeNoderoot, longtargetSum) {

       if(root==null) return0;

       returndfs(root,targetSum)+pathSum(root.left,targetSum)+pathSum(root.right,targetSum);

   }

   publicintdfs(TreeNoderoot, longtargetSum){

       if(root==null) return0;

       intres=0;

       if(root.val==targetSum)

           res++;

       returnres+dfs(root.left,targetSum-root.val)+dfs(root.right,targetSum-root.val);

   }

}

classSolution {

   privateintres;

   publicintpathSum(TreeNoderoot, inttargetSum) {      

       if(root==null) returnres;

       help(root,targetSum);

       pathSum(root.left,targetSum);

       pathSum(root.right,targetSum);

       returnres;

   }

   publicvoidhelp(TreeNoderoot,inttarget){

       if(root==null) return;

       if(root.val==target) res++;

       help(root.left,target-root.val);

       help(root.right,target-root.val);

   }

}

前缀和解法

classSolution {

   publicintpathSum(TreeNoderoot, longtargetSum) {

       Map<Long, Integer>prefix=newHashMap<Long, Integer>();

       prefix.put(0L, 1);

       returndfs(root, prefix, 0, targetSum);

   }

   publicintdfs(TreeNoderoot,Map<Long,Integer>prefix,longcur,longtarget){

       if (root==null) return0;

       intres=0;

       cur+=root.val; //当前节点的前缀和

       res=prefix.getOrDefault(cur-target,0);

       prefix.put(cur,prefix.getOrDefault(cur,0)+1);

       res+=dfs(root.left,prefix,cur,target);

       res+=dfs(root.right,prefix,cur,target);

       //回溯

       prefix.put(cur,prefix.getOrDefault(cur,0)-1);

       returnres;

 

   }

}

二叉树中的最大路径和

遍历顺序为后序遍历,左右中,先把左右节点的最大值获取到,将当前节点作为拐点,连接左右两个节点,更新路径最大值后,返会当前节点+Math.max(左节点,右节点),也就是返会当前节点获得的最大值

classSolution {

   intmax=Integer.MIN_VALUE;

   publicintmaxPathSum(TreeNoderoot) {

       dfs(root);

       returnmax;

   }

   publicintdfs(TreeNoderoot){

       if (root==null) return0;

       intLeftMax=Math.max(dfs(root.left),0);//返会当前节点右节点的最大值

       intRightMax=Math.max(dfs(root.right),0);//返回当前节点左节点的最大值

       max=Math.max(max,root.val+LeftMax+RightMax);//更新路径的最大值

       returnroot.val+Math.max(LeftMax,RightMax);//返回当前节点的最大值  

   }

}


相关文章
|
10天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
13 1
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
30天前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
19 2
|
30天前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
15 2
|
30天前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
14 2
|
30天前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
17 0
|
30天前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
13 0
|
30天前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
12 0
|
30天前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
11 0
|
30天前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
15 0