題目

給定一棵二叉樹和一個(gè)值sum，求二叉樹中節(jié)點(diǎn)值之和等于sum的路徑的數(shù)目。路徑的定義為二叉樹中順著指向子節(jié)點(diǎn)的指針向下移動(dòng)所經(jīng)過(guò)的節(jié)點(diǎn)，但不一定從根節(jié)點(diǎn)開始，也不一定到葉節(jié)點(diǎn)結(jié)束。例如，在如圖8.5所示中的二叉樹中有兩條路徑的節(jié)點(diǎn)值之和等于8，其中，第1條路徑從節(jié)點(diǎn)5開始經(jīng)過(guò)節(jié)點(diǎn)2到達(dá)節(jié)點(diǎn)1，第2條路徑從節(jié)點(diǎn)2開始到節(jié)點(diǎn)6。

分析

雖然路徑不一定從根節(jié)點(diǎn)開始，但仍然可以求得從根節(jié)點(diǎn)開始到達(dá)當(dāng)前遍歷節(jié)點(diǎn)的路徑所經(jīng)過(guò)的節(jié)點(diǎn)值之和。

如果在路徑上移動(dòng)時(shí)把所有累加的節(jié)點(diǎn)值之和都保存下來(lái)，然后移動(dòng)的過(guò)程中求差值，就容易知道是否存在從任意節(jié)點(diǎn)出發(fā)的值為給定sum的路徑。

有了前面的經(jīng)驗(yàn)，就可以采用二叉樹深度優(yōu)先搜索來(lái)解決與路徑相關(guān)的問(wèn)題。當(dāng)遍歷到一個(gè)節(jié)點(diǎn)時(shí)，先累加從根節(jié)點(diǎn)開始的路徑上的節(jié)點(diǎn)值之和，再計(jì)算到它的左右子節(jié)點(diǎn)的路徑的節(jié)點(diǎn)值之和。這就是典型的前序遍歷的順序。

解

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) {Map<Integer, Integer> map = new HashMap<>();map.put(0, 1);// 節(jié)點(diǎn)和為0的路徑有一個(gè)（空路徑）// path: 遍歷節(jié)點(diǎn)的路徑和return dfs(root, sum, map, 0);}private static int dfs(TreeNode root, int sum, Map<Integer, Integer> map, int path) {if (root == null) {return 0;}// 前序遍歷path += root.val;int count = map.getOrDefault(path - sum, 0);// 深度優(yōu)先遍歷，如果以前存在這個(gè)差值，那么和當(dāng)前路徑一定是以前路徑的延伸map.put(path, map.getOrDefault(path, 0) + 1);count += dfs(root.left, sum, map, path);count += dfs(root.right, sum, map, path);// 當(dāng)前這個(gè)節(jié)點(diǎn)遍歷完成，重回當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)繼續(xù)遍歷。map.put(path, map.get(path) - 1);return count;}
}