Description

面试题34. 二叉树中和为某一值的路径

难度：中等
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:给定如下二叉树，以及目标和 sum = 22

  1.               5
  2.              / \
  3.             4   8
  4.            /   / \
  5.           11  13  4
  6.          /  \    / \
  7.         7    2  5   1

返回:

  1. [
  2.    [5,4,11,2],
  3.    [5,8,4,5]
  4. ]

提示：

  1. 节点总数 <= 10000

解答：
前序遍历的思路
维护一个 sum（路径的和），每次遍历将当前节点的值

  1. class Solution {
  2.     List<List<Integer>> paths;
  3.     List<Integer> temp;
  4.     int sum; 
  5.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
  6.         paths = new ArrayList<>();
  7.         temp = new ArrayList<>();
  8.         this.sum = sum;
  9.         preOrder(root, 0);
  10.         return paths;
  11.     }
  12.     public void preOrder(TreeNode node, int sum){
  13.         if(node == null) 
  14.             return;
  15.         // 计算和
  16.         sum += node.val; 
  17.         temp.add(node.val);
  18.         // 如果 sum 等于指定的值，且当前节点为叶子节点时
  19.         if(sum == this.sum && node.right == null && node.left == null){
  20.             paths.add(temp);
  21.             temp = new ArrayList<>(temp);
  22.         }
  23.         preOrder(node.left, sum);
  24.         preOrder(node.right, sum);
  25.         temp.remove(temp.size()-1);  // 返回上一节点时，删除 list 中当前节点的值
  26.     }
  27. }