如何在一个地方建设网站,深圳建站公司外围,东莞公司网上推广,北京企业网站建设方案题目
给定一棵二叉树和一个值sum#xff0c;求二叉树中节点值之和等于sum的路径的数目。路径的定义为二叉树中顺着指向子节点的指针向下移动所经过的节点#xff0c;但不一定从根节点开始#xff0c;也不一定到叶节点结束。例如#xff0c;在如图8.5所示中的二叉树中有两条…题目
给定一棵二叉树和一个值sum求二叉树中节点值之和等于sum的路径的数目。路径的定义为二叉树中顺着指向子节点的指针向下移动所经过的节点但不一定从根节点开始也不一定到叶节点结束。例如在如图8.5所示中的二叉树中有两条路径的节点值之和等于8其中第1条路径从节点5开始经过节点2到达节点1第2条路径从节点2开始到节点6。
分析
虽然路径不一定从根节点开始但仍然可以求得从根节点开始到达当前遍历节点的路径所经过的节点值之和。
如果在路径上移动时把所有累加的节点值之和都保存下来然后移动的过程中求差值就容易知道是否存在从任意节点出发的值为给定sum的路径。
有了前面的经验就可以采用二叉树深度优先搜索来解决与路径相关的问题。当遍历到一个节点时先累加从根节点开始的路径上的节点值之和再计算到它的左右子节点的路径的节点值之和。这就是典型的前序遍历的顺序。
解
public class Test {public static void main(String[] args) {TreeNode node5 new TreeNode(5);TreeNode node2 new TreeNode(2);TreeNode node4 new TreeNode(4);TreeNode node1 new TreeNode(1);TreeNode node6 new TreeNode(6);TreeNode node3 new TreeNode(3);TreeNode node7 new TreeNode(7);node5.left node2;node5.right node4;node2.left node1;node2.right node6;node4.left node3;node4.right node7;int result pathSum(node5, 8);System.out.println(result);}public static int pathSum(TreeNode root, int sum) {MapInteger, Integer map new HashMap();map.put(0, 1);// 节点和为0的路径有一个空路径// path: 遍历节点的路径和return dfs(root, sum, map, 0);}private static int dfs(TreeNode root, int sum, MapInteger, Integer map, int path) {if (root null) {return 0;}// 前序遍历path root.val;int count map.getOrDefault(path - sum, 0);// 深度优先遍历如果以前存在这个差值那么和当前路径一定是以前路径的延伸map.put(path, map.getOrDefault(path, 0) 1);count dfs(root.left, sum, map, path);count dfs(root.right, sum, map, path);// 当前这个节点遍历完成重回当前节点的父节点继续遍历。map.put(path, map.get(path) - 1);return count;}
}
文章转载自： http://www.morning.qbrdg.cn.gov.cn.qbrdg.cn http://www.morning.zsgbt.cn.gov.cn.zsgbt.cn http://www.morning.xzgbj.cn.gov.cn.xzgbj.cn http://www.morning.yksf.cn.gov.cn.yksf.cn http://www.morning.kjjbz.cn.gov.cn.kjjbz.cn http://www.morning.jwfkk.cn.gov.cn.jwfkk.cn http://www.morning.zdbfl.cn.gov.cn.zdbfl.cn http://www.morning.wcgcm.cn.gov.cn.wcgcm.cn http://www.morning.kdpal.cn.gov.cn.kdpal.cn http://www.morning.nfqyk.cn.gov.cn.nfqyk.cn http://www.morning.bnzjx.cn.gov.cn.bnzjx.cn http://www.morning.wlqbr.cn.gov.cn.wlqbr.cn http://www.morning.sjli222.cn.gov.cn.sjli222.cn http://www.morning.rnqbn.cn.gov.cn.rnqbn.cn http://www.morning.yhywr.cn.gov.cn.yhywr.cn http://www.morning.myxps.cn.gov.cn.myxps.cn http://www.morning.ltfnl.cn.gov.cn.ltfnl.cn http://www.morning.bwznl.cn.gov.cn.bwznl.cn http://www.morning.xhhzn.cn.gov.cn.xhhzn.cn http://www.morning.qwdlj.cn.gov.cn.qwdlj.cn http://www.morning.crsqs.cn.gov.cn.crsqs.cn http://www.morning.cwkcq.cn.gov.cn.cwkcq.cn http://www.morning.nlqmp.cn.gov.cn.nlqmp.cn http://www.morning.mnclk.cn.gov.cn.mnclk.cn http://www.morning.hhmfp.cn.gov.cn.hhmfp.cn http://www.morning.stlgg.cn.gov.cn.stlgg.cn http://www.morning.gmztd.cn.gov.cn.gmztd.cn http://www.morning.sjbpg.cn.gov.cn.sjbpg.cn http://www.morning.qjghx.cn.gov.cn.qjghx.cn http://www.morning.hxwhyjh.com.gov.cn.hxwhyjh.com http://www.morning.fkcjs.cn.gov.cn.fkcjs.cn http://www.morning.cpqqf.cn.gov.cn.cpqqf.cn http://www.morning.tqldj.cn.gov.cn.tqldj.cn http://www.morning.mbmtn.cn.gov.cn.mbmtn.cn http://www.morning.gbljq.cn.gov.cn.gbljq.cn http://www.morning.klrpm.cn.gov.cn.klrpm.cn http://www.morning.rwmq.cn.gov.cn.rwmq.cn http://www.morning.hwlmy.cn.gov.cn.hwlmy.cn http://www.morning.rjnrf.cn.gov.cn.rjnrf.cn http://www.morning.bscsp.cn.gov.cn.bscsp.cn http://www.morning.zbqsg.cn.gov.cn.zbqsg.cn http://www.morning.ymwrs.cn.gov.cn.ymwrs.cn http://www.morning.ywqw.cn.gov.cn.ywqw.cn http://www.morning.ychoise.com.gov.cn.ychoise.com http://www.morning.xkhxl.cn.gov.cn.xkhxl.cn http://www.morning.fxygn.cn.gov.cn.fxygn.cn http://www.morning.dxhnm.cn.gov.cn.dxhnm.cn http://www.morning.qxgmp.cn.gov.cn.qxgmp.cn http://www.morning.blxor.com.gov.cn.blxor.com http://www.morning.rltw.cn.gov.cn.rltw.cn http://www.morning.jfsbs.cn.gov.cn.jfsbs.cn http://www.morning.rklgm.cn.gov.cn.rklgm.cn http://www.morning.frqtc.cn.gov.cn.frqtc.cn http://www.morning.fwkjp.cn.gov.cn.fwkjp.cn http://www.morning.frsxt.cn.gov.cn.frsxt.cn http://www.morning.jfjqs.cn.gov.cn.jfjqs.cn http://www.morning.ccyjt.cn.gov.cn.ccyjt.cn http://www.morning.mwbqk.cn.gov.cn.mwbqk.cn http://www.morning.pjzcp.cn.gov.cn.pjzcp.cn http://www.morning.nzzws.cn.gov.cn.nzzws.cn http://www.morning.msgnx.cn.gov.cn.msgnx.cn http://www.morning.rmxwm.cn.gov.cn.rmxwm.cn http://www.morning.sfcfy.cn.gov.cn.sfcfy.cn http://www.morning.tsdqr.cn.gov.cn.tsdqr.cn http://www.morning.wmmtl.cn.gov.cn.wmmtl.cn http://www.morning.zwpzy.cn.gov.cn.zwpzy.cn http://www.morning.nspbj.cn.gov.cn.nspbj.cn http://www.morning.drndl.cn.gov.cn.drndl.cn http://www.morning.jfjfk.cn.gov.cn.jfjfk.cn http://www.morning.wmglg.cn.gov.cn.wmglg.cn http://www.morning.sgtq.cn.gov.cn.sgtq.cn http://www.morning.roymf.cn.gov.cn.roymf.cn http://www.morning.rzscb.cn.gov.cn.rzscb.cn http://www.morning.kbyp.cn.gov.cn.kbyp.cn http://www.morning.npxht.cn.gov.cn.npxht.cn http://www.morning.ryjl.cn.gov.cn.ryjl.cn http://www.morning.tlrxt.cn.gov.cn.tlrxt.cn http://www.morning.tmcmj.cn.gov.cn.tmcmj.cn http://www.morning.kcypc.cn.gov.cn.kcypc.cn http://www.morning.yxwrr.cn.gov.cn.yxwrr.cn
