題目

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

分析

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

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

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

解

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é)點和為0的路徑有一個（空路徑）// path: 遍歷節(jié)點的路徑和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)先遍歷，如果以前存在這個差值，那么和當(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)前這個節(jié)點遍歷完成，重回當(dāng)前節(jié)點的父節(jié)點繼續(xù)遍歷。map.put(path, map.get(path) - 1);return count;}
}