thanlau

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }

thanlau

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }

thanlau

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**

thanlau

//define linkedNode
class LinkedNode{
    int val;
    LinkedNode next;
    public LinkedNode(int val){
        this.val = val;
        this.next = next;
    }
}

thanlau

首先，样例的答案是：[[2,1,3],[2,4],[3,1,2],[4,2]]。（中文版面有问题，已反馈）
1.首先，我们观察样例，发现相同的路径点，走的顺序不一样，就视为不同的路径；同一个点，只能走一次，不能重复走。
2.既然这样，那我们就有一个最简单的思路，枚举树上的点，以该点为起点搜索可行的路径。
3.dfs(root, target, results)：遍历整棵二叉树，当前遍历到的点是root。
目标值为target，所有可行路径存储在results中。
4.findSum(root, father, target, path, results);
搜索以root为起点，目标值为target的可行路径，并将搜索路径存储在path中。当target为0时，即代表该搜索路径为一条可行路径，将其存入答案results中。
当root为路径起点时，father为空，此时可以向三个方向进行搜索（父亲节点、左儿子节点、右儿子节点）。
当root不是路径起点时，此时的father为搜索路径中，root的上一个点，只能向三个方向中，非father的两个方向进行搜索。
5.最后要注意的就是数据的问题了，题上并没有说数据都是正整数，所以是有可能存在负值和0的。

thanlau

我的问题：一开始我不会多叉树如何表示其子节点
list<TreeNode> children; root.children用来表示根的所有子节点
for (MultiTreeNode child : root.children)用来表示遍历root的所有子树

/**
 * Definition for a multi tree node.
 * public class MultiTreeNode {
 *     int val;
 *     List<TreeNode> children;
 *     MultiTreeNode(int x) { val = x; }

thanlau

我的错误解法
    1
   / \
  2   0
 / \
3   1
这里helper(root.left)他意思是从根节点一直往下走。那么例如1过了，到了2，
第一，二个if我是找左子树往上走和往下走和往上走的最长路径,这里helper(root.left)他意思是从根节点一直往下走。那么例如1过了，到了2，
root.left.val + 1 ==root.val，root.left.val - 1 ==root.val 是看2的左子树是递增还是递减，在这里是递增，因此，root.left.val - 1 ==root.val成立
2的右子树正好递减，因此root.right.val+1 = root.val成立，但是我在例如第一个判断出来递减的时候

thanlau

public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
        /**思路
         * 起点不一定在root上面，那么可以从叶子节点逐步向上走
         * for循环找到等于target的路径输出*/

thanlau

public class Solution {
    //
     private class ResultType{
        public int sum;
        public ArrayList<Integer> path;
        public ResultType(int sum, ArrayList<Integer> path){
            this.sum = sum;
            this.path = path;
        }
    }

thanlau

/**
 * 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;
 *     }
 * }