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

题目链接

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

437. 路径总和 III - 力扣（LeetCode）

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

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

三种解法

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

class Solution {public int sumNumbers(TreeNode root) {return dfs(root,0);}public int dfs(TreeNode root,int sum){// sum存储的是每一条路径的和if(root == null) return 0;sum = sum *10 + root.val;if(root.left == null && root.right == null) return sum;//返会这条路径的值else return dfs(root.left,sum)+dfs(root.right,sum); //将左右节点的路径加和}
}

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

class Solution {int sum = 0,num = 0;public int sumNumbers(TreeNode root) {dfs(root);return sum;}public void dfs(TreeNode root){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;}
}

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

class Solution {public int sumNumbers(TreeNode root) {Deque<TreeNode> deq1 = new ArrayDeque();Deque<Integer> deq2 = new ArrayDeque();deq1.add(root);deq2.add(root.val);int sum = 0;while(!deq1.isEmpty()){TreeNode node = deq1.poll();int num = 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);}}return sum;}
}

路径总和 III

class Solution {public int pathSum(TreeNode root, long targetSum) {if(root == null) return 0;return dfs(root,targetSum)+pathSum(root.left,targetSum)+pathSum(root.right,targetSum);}public int dfs(TreeNode root, long targetSum){if(root == null) return 0;int res = 0;if(root.val == targetSum)res ++;return res + dfs(root.left,targetSum-root.val)+dfs(root.right,targetSum-root.val);}
}

class Solution {private int res;public int pathSum(TreeNode root, int targetSum) {      if(root==null) return res;help(root,targetSum);pathSum(root.left,targetSum);pathSum(root.right,targetSum);return res;}public void help(TreeNode root,int target){if(root==null) return;if(root.val==target) res++;help(root.left,target-root.val);help(root.right,target-root.val);}
}

前缀和解法

class Solution {public int pathSum(TreeNode root, long targetSum) {Map<Long, Integer> prefix = new HashMap<Long, Integer>();prefix.put(0L, 1);return dfs(root, prefix, 0, targetSum);}public int dfs(TreeNode root,Map<Long,Integer> prefix,long cur,long target){if (root == null) return 0;int res = 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);return res;}
}

二叉树中的最大路径和

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

class Solution {int max = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return max;}public int dfs(TreeNode root){if (root == null) return 0;int LeftMax = Math.max(dfs(root.left),0);//返会当前节点右节点的最大值int RightMax = Math.max(dfs(root.right),0);//返回当前节点左节点的最大值max = Math.max(max,root.val+LeftMax+RightMax);//更新路径的最大值return root.val + Math.max(LeftMax,RightMax);//返回当前节点的最大值  }
}