leetcode刷题 | 关于二叉树的题型总结2
题目链接
129. 求根节点到叶节点数字之和 - 力扣（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);//返回当前节点的最大值
}
}
