113. Path Sum II
利用DFS的三要素， 出口1，出口2，拆解，记得回溯的时候要回退一位path。
class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> res = new ArrayList<>(); dfs(res, new ArrayList<Integer>(), sum, root); return res; } private void dfs(List<List<Integer>> res, List<Integer> path, int sum, TreeNode root){ if(root == null) return; sum -= root.val; //leaf node? if(root.left == null && root.right == null){ if(sum == 0){ path.add(root.val); res.add(new ArrayList<Integer>(path)); path.remove(path.size() - 1); } return; } //拆解 path.add(root.val); dfs(res, path, sum, root.left); dfs(res, path, sum, root.right); path.remove(path.size() - 1); } }
129. Sum Root to Leaf Numbers
都是利用DFS递归来解，这道题由于不是单纯的把各个节点的数字相加，而是每遇到一个新的子结点的数字，要把父结点的数字扩大10倍之后再相加。如果遍历到叶结点了，就将当前的累加结果sum返回。如果不是，则对其左右子结点分别调用递归函数，将两个结果相加返回即可
class Solution { public int sumNumbers(TreeNode root) { return dfs(0, root); } private int dfs(int sum, TreeNode root){ if(root == null) return 0; sum = sum * 10 + root.val; if(root.left == null && root.right == null){ return sum; } return dfs(sum, root.left) + dfs(sum, root.right); } }
原文：https://www.cnblogs.com/Afei-1123/p/11897666.html