Description

Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.

A valid path is from root node to any of the leaf nodes.

Example

Given a binary tree, and target = 5:

1    / \   2   4  / \ 2   3

return

[  [1, 2, 2],  [1, 4]]

解题：给一个二叉树，找到和是给定目标值的支路。如果不用栈，需要考虑一下回溯算法的运用，代码如下：

/** * Definition of TreeNode: * public class TreeNode { *     public int val; *     public TreeNode left, right; *     public TreeNode(int val) { *         this.val = val; *         this.left = this.right = null; *     } * } */public class Solution {    /*     * @param root: the root of binary tree     * @param target: An integer     * @return: all valid paths     */    int target = 0;    List
        
         
          > res = new ArrayList<>();    public List
          
           
            > binaryTreePathSum(TreeNode root, int target) {        // write your code here        if(root == null){            return res;        }        this.target = target;        List
            
             path = new ArrayList<>();        helper(path, root, 0);        return res;    }    public void helper(List
             
              path, TreeNode root, int sum){ sum +=root.val; path.add(root.val); //如果到叶子结点了，并且和为target if(root.left == null && root.right == null && sum == target){ ArrayList
              
               temp = new ArrayList<>(); temp.addAll(path);//复制一份 res.add(temp); } if(root.left != null){ helper(path, root.left, sum); } if(root.right != null){ helper(path, root.right, sum); } path.remove(path.size() - 1); }}