给定一个二叉树root和一个整数值 sum ,求该树有多少路径的的节点值之和等于 sum 。
1.该题路径定义不需要从根节点开始,也不需要在叶子节点结束,但是一定是从父亲节点往下到孩子节点
2.总节点数目为n
3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)
数据范围:
假如二叉树root为{1,2,3,4,5,4,3,#,#,-1},sum=6,那么总共如下所示,有3条路径符合要求
{1,2,3,4,5,4,3,#,#,-1},6
3
如图所示,有3条路径符合
{0,1},1
2
{1,#,2,#,3},3
2
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @param sum int整型 * @return int整型 */ int res = 0; public void getPath(TreeNode cur, int sum) { if (cur == null) { return; } sum-=cur.val; if (sum == 0) { res++; } getPath(cur.left, sum); getPath(cur.right, sum); } public int FindPath (TreeNode root, int sum) { // write code here if (root == null) { return 0; } Queue<TreeNode> que = new ArrayDeque<>(); que.add(root); while (!que.isEmpty()) { int n = que.size(); for (int i = 0; i < n; i++) { TreeNode cur = que.poll(); getPath(cur, sum); if (cur.left != null) { que.add(cur.left); } if (cur.right != null) { que.add(cur.right); } } } return res; } }
import java.util.*; public class Solution { int res = 0; int target = 0; public int FindPath (TreeNode root, int sum) { target = sum; if (root == null) return 0; midOrder(root); return res; } private void midOrder(TreeNode root) { if (root != null) { midOrder(root.left); bfs(root, 0); midOrder(root.right); } } private void bfs(TreeNode root, int sum) { if (root == null) return; if (sum + root.val == target) { res ++; } bfs(root.left, sum + root.val); bfs(root.right, sum + root.val); } }
import java.util.*; /* * public class TreeNode { * int val = 0;l * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @param sum int整型 * @return int整型 */ //利用前缀和解决 public int FindPath (TreeNode root, int sum) { if(root==null && sum!=0) return 0; HashMap<Long,Integer> map=new HashMap<>(); map.put(0L,1); //给每个节点自己凑和的机会 int count=0; count=digui(root,map,sum,0); return count; } /** cur 到目前位置,根节点到本节点时候的前缀和 */ public int digui(TreeNode root,HashMap<Long,Integer> map,int sum,long cur){ if(root==null) return 0; cur+=root.val; int res=map.getOrDefault(cur-sum,0); map.put(cur,map.getOrDefault(cur,0)+1); res+=digui(root.left,map,sum,cur); res+=digui(root.right,map,sum,cur); map.put(cur,map.getOrDefault(cur,0)-1); return res; } }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param root TreeNode类 * @param sum int整型 * @return int整型 */ int res = 0; public int FindPath(TreeNode root, int sum) { if (root == null) { return res; } FindPath(root.left, sum); show(root,0,sum); FindPath(root.right, sum); return res; } public void show(TreeNode node, int now ,int sum) { now += node.val; if (now == sum) { res++; } if (node.left != null) { show(node.left,now,sum); } if (node.right != null) { show(node.right,now,sum); } } }
public class Solution { //当sum为0时不能返回,所以就只能声明在外面在递归里面+1 int res = 0; public int FindPath (TreeNode root, int sum) { if(root == null){ return 0; } dfs(root, sum); FindPath(root.left, sum); FindPath(root.right, sum); return res; } public void dfs (TreeNode root, int sum) { if(root == null){ return ; } sum -= root.val; //当sum为0时不能返回,因为后面也可能会有符合条件的 if(sum == 0){ res++; } dfs(root.left, sum); dfs(root.right, sum); } }
public class Solution { private int ans = 0; private int preSum = 0; HashMap<Integer, Integer> map; public int FindPath (TreeNode root, int sum) { // write code here if (root == null) { return 0; } map = new HashMap<>(); map.put(0, 1); process(root, sum); return ans; } public void process(TreeNode root, int sum) { if (root == null) { return; } preSum += root.val; if (map.containsKey(preSum - sum)) { ans += map.get(preSum - sum); } if (map.containsKey(preSum)) { map.put(preSum, map.get(preSum) + 1); }else { map.put(preSum, 1); } process(root.left, sum); process(root.right, sum); map.put(preSum, map.get(preSum) - 1); preSum -= root.val; } }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @param sum int整型 * @return int整型 */ private int pathNum = 0; public int FindPath (TreeNode root, int sum) { // write code here if (root == null) return pathNum; dfs(root, sum); return pathNum; } public void pathFromOneNode (TreeNode root, int expectedNum) { if (root == null) return; if (root.val == expectedNum) pathNum++; if (root.left != null) { pathFromOneNode(root.left, expectedNum - root.val); } if (root.right != null) { pathFromOneNode(root.right, expectedNum - root.val); } } public void dfs(TreeNode root, int expectedNum){ pathFromOneNode(root, expectedNum); if (root.left != null) dfs(root.left, expectedNum); if (root.right != null) dfs(root.right, expectedNum); } }
private int path; public int FindPath (TreeNode root, int sum) { if (root == null) { return 0; } // write code here Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode t = stack.pop(); visit(t, sum); if (t.right != null) { stack.push(t.right); } if (t.left != null) { stack.push(t.left); } } return path; } private void visit(TreeNode root, int sum) { if (root == null) { return; } sum -= root.val; if (sum == 0) { path++; } visit(root.left, sum); visit(root.right, sum); }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @param sum int整型 * @return int整型 */ public static int res = 0;//统计路径个数 public int FindPath (TreeNode root, int sum) { if(root == null){ return 0; } show(root,sum); return res; } //遍历每个节点 public void show(TreeNode root, int sum){ if(root == null){ return; } func(root,0,sum); if(root.left != null){ show(root.left,sum); } if(root.right != null){ show(root.right,sum); } } //对传进来的节点为根,进行查找,找到满足条件的路径,并记录结果。 //当每条路走到叶子节点处,就返回 public void func(TreeNode root, int count,int sum){ count +=root.val; if(sum == count){ res=res+1; } if(root.left != null ){ func(root.left,count,sum); } if(root.right != null ){ func(root.right,count,sum); } if(root.left == null && root.left == null){ return; } } }
public int FindPath (TreeNode root, int sum) { // write code here // FindPath 方法定义为从 root 节点开始,必须包括 root 节点,有多少路径的和为 sum if (root == null) { return 0; } dfs(root, sum, 0); FindPath(root.left, sum); FindPath(root.right, sum); return ans; } private int ans; public void dfs(TreeNode root, int sum, int target) { if (root == null) { return ; } target += root.val; if (target == sum) { ans ++; } dfs(root.left, sum, target); dfs(root.right, sum, target); target -= root.val; }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @param sum int整型 * @return int整型 */ int num; //总数量 public int FindPath (TreeNode root, int sum) { if (root==null) return num; Deque<TreeNode> deque = new ArrayDeque<>(); deque.add(root); while (!deque.isEmpty()) { int size = deque.size(); for (int i = 0; i < size; ++i) { TreeNode pollNode = deque.poll(); toFindPath(pollNode,sum-pollNode.val); if (pollNode.left!=null) deque.add(pollNode.left); if (pollNode.right!=null) deque.add(pollNode.right); } } return num; } private void toFindPath(TreeNode root, int target) { if (target==0) { ++num; } if(root.left!=null) toFindPath(root.left,target-root.left.val); if(root.right!=null) toFindPath(root.right,target-root.right.val); } }
public class JZ84_FindPath { int key = 0; public int FindPath (TreeNode root, int sum) { if (root == null) return key; find(root,sum); FindPath(root.left,sum); FindPath(root.right,sum); return key; } public void find(TreeNode root, int sum){ if (root == null) return; sum -= root.val; if (sum == 0) key++; find(root.left,sum); find(root.right,sum); } }