做肯德基玻璃门网站,铜山区规划建设局网站,洪梅镇仿做网站,wordpress如何双语提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣1602. 找到二叉树中最近的右侧节点二、力扣437. 路径总和 III三、力扣560. 和为 K 的子数组 前言 二叉树的递归分为「遍历」和「分解问题」两种思维模式… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣1602. 找到二叉树中最近的右侧节点二、力扣437. 路径总和 III三、力扣560. 和为 K 的子数组 前言 二叉树的递归分为「遍历」和「分解问题」两种思维模式这道题需要用到「遍历」的思维模式
一、力扣1602. 找到二叉树中最近的右侧节点
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {int dif Integer.MAX_VALUE;TreeNode res null;int high -1;int flag -1;public TreeNode findNearestRightNode(TreeNode root, TreeNode u) {fun(root, u, 1,1);return res;}public void fun(TreeNode root, TreeNode u, int index, int depth){if(root null){return;}if(root u){high depth;flag index;}else if(high depth){if((index - flag) dif){res root;dif index - flag;}}fun(root.left , u, index * 2, depth 1);fun(root.right, u, index *2 1, depth 1);}
}二、力扣437. 路径总和 III
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {MapLong,Integer preSumPath new HashMap();int res 0;long targetSum , pathSum ;public int pathSum(TreeNode root, int targetSum) {if(root null){return 0;}this.targetSum targetSum;this.pathSum 0;preSumPath.put(0L,1);fun(root);return res;}public void fun(TreeNode root){if(root null){return;}pathSum root.val;res preSumPath.getOrDefault(pathSum - targetSum,0);preSumPath.put(pathSum, preSumPath.getOrDefault(pathSum,0)1);fun(root.left);fun(root.right);preSumPath.put(pathSum,preSumPath.getOrDefault(pathSum,0)-1);pathSum - root.val;}
}三、力扣560. 和为 K 的子数组
class Solution {public int subarraySum(int[] nums, int k) {int[] preSum new int[nums.length1];for(int i 0; i nums.length; i ){preSum[i1] nums[i] preSum[i];}int count 0;for(int low 0; low preSum.length - 1; low ){for(int high low; high preSum.length-1; high ){if(preSum[high 1] - preSum[low] k){count ;}}}return count;}
}
