LintCode 376 - Binary Tree Path Sum

https://xuezhashuati.blogspot.com/2016/02/binary-tree-path-sum.html
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]
]

http://www.szeju.com/index.php/other/35241410.html

public List<String> binaryTreePaths(TreeNode root) { List<String> result = new ArrayList<>(); List<Integer> list = new ArrayList<>(); if (root == null) { return result; } list.add(root.val); helper(root, list, result); return result; } private void helper(TreeNode root, List<Integer> list, List<String> result) { if (root.left == null && root.right == null) { result.add(toStr(new ArrayList<Integer>(list))); } if (root.left != null) { list.add(root.left.val); helper(root.left, list, result); list.remove(list.size() - 1); } if (root.right != null) { list.add(root.right.val); helper(root.right, list, result); list.remove(list.size() - 1); } } private String toStr(List<Integer> list) { StringBuilder sb = new StringBuilder(); sb.append(list.get(0)); for (int i = 1; i < list.size(); i++) { sb.append("->"); sb.append(list.get(i)); } return sb.toString(); }

DFS + Backtracking从root往下遍历。如果发现sum == target并且已经走到底了，就把这坨序列加到result里。

    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        // Write your code here
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        list.add(root.val);
        helper(root, target, result, list, root.val);
        return result;
    }
    
    public void helper(TreeNode root, 
                       int target, 
                       List<List<Integer>> result, 
                       List<Integer> list, 
                       int sum) {
                           
        if (root == null) {
            return;
        }
        
        if (root.left == null && root.right == null && sum == target) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        
        if (root.left != null) {
            list.add(root.left.val);
            helper(root.left, target, result, list, sum + root.left.val);
            list.remove(list.size() - 1);
        }
        
        if (root.right != null) {
            list.add(root.right.val);
            helper(root.right, target, result, list, sum + root.right.val);
            list.remove(list.size() - 1);
        }
    }

http://blog.csdn.net/jason__liang/article/details/64165887
static public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) { // Write your code here List<List<Integer>> ret=new ArrayList<>(); ArrayList<Integer> linshi=new ArrayList<>(); int sum=root.val; preordertravel(root,ret,target,linshi,sum); return ret; } static void preordertravel(TreeNode root,List<List<Integer>> ret,int target,ArrayList<Integer> linshi,int sum) { if(sum==target&&root!=null&&root.left==null&&root.right==null) { linshi.add(root.val); ret.add(new ArrayList<>(linshi)); linshi.remove(linshi.size()-1); } else { if(root!=null) { linshi.add(root.val); preordertravel(root.left, ret, target, linshi, root.left==null?sum:sum+root.left.val); preordertravel(root.right, ret, target, linshi, root.right==null?sum:sum+root.right.val); linshi.remove(linshi.size()-1); } } }

http://www.szeju.com/index.php/other/35241410.html

public List<String> binaryTreePaths(TreeNode root) { List<String> result = new ArrayList<>(); if (root == null) { return result; } List<String> left = binaryTreePaths(root.left); List<String> right = binaryTreePaths(root.right); for (String l : left) { result.add(root.val + "->" + l); } for (String r : right) { result.add(root.val + "->" + r); } if (result.size() == 0) { result.add("" + root.val); } return result; }