leetcode__2_0">leetcode刷题 | 关于二叉树的题型总结2
文章目录
- leetcode刷题 | 关于二叉树的题型总结2
- 题目链接
- 求根节点到叶节点数字之和
- 路径总和 III
- 二叉树中的最大路径和
题目链接
129. 求根节点到叶节点数字之和 - 力扣(LeetCode)
437. 路径总和 III - 力扣(LeetCode)
124. 二叉树中的最大路径和 - 力扣(LeetCode)
求根节点到叶节点数字之和
三种解法
第一种带有返回值的dfs,返回值为某一路径的值
java">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); //将左右节点的路径加和
}
}
第二种不带返回值的递归+回溯
java">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;
}
}
第三种广度优先搜索,定义两个栈,一个存储节点一个存储节点值
java">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
java">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);
}
}
java">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);
}
}
前缀和解法
java">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(左节点,右节点),也就是返会当前节点获得的最大值
java">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);//返回当前节点的最大值
}
}