求二叉树满足条件路径

问题

给定二叉树，求的某一路径满足所有节点和为某一个值

分析

采用递归，定义一个方法List getPath(Node root, int target),从root开始，首先判断root.val是否大于target，如果大于说明这个路径不可能成功，返回一个空的List就可以，如果小，那么target -= val，然后递归左右节点，如果返回的List不空，那么说明满足，就可以add自己进path了。其实递归的实质，就是从叶子结点开始向上计算，所以返回的List应该是从叶子节点创建的，我们在程序中需要特殊判断叶子结点。代码如下

import java.util.ArrayList;
/*
 public class TreeNode {
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val) {
 this.val = val;

 }
 */

 }
public class Solution {
    public ArrayList<Integer> FindPath(TreeNode root,int target) {
        ArrayList<Integer> data = new ArrayList<>();
        // 非法节点,返回空list
        if (root == null || root.val > target) {
            return data;
        }
        // 叶子结点
        if (root.left == null && root.right == null) {
            // 不满足，返回空list
            if (root.val != target) {
                return data;
            }
            // 满足就add，返回
            data.add(root.val);
            return data;
        }
        // 普通节点
        target -= root.val;
        ArrayList<Integer> l = FindPath(root.left, target);
        if (l.size() != 0) {
            // 返回非空，满足
            l.add(root.val);
            return l;
        }
        ArrayList<Integer> r = FindPath(root.right, target);
        if (r.size() != 0) {
            // 返回非空，满足
            r.add(root.val);
            return r;
        }
        // 左右节点均不满足,返回空list
        return data;
    }
}

扩展

前面我们只需要找到一条就可以了，但是如果要求我们找到所有呢？思路其实一样，只不过变成List<List>而已，而且每次从左右节点获得的结果如果size != 0，那么就要把里面每一条path都add自己，然后把这两个结果合并返回，代码如下

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> data = new ArrayList<>();
        // 非法节点
        if (root == null || root.val > target) {
            return data;
        }
        // 叶子结点
        if (root.left == null && root.right == null) {
            if (root.val != target) {
                return data;
            }
            ArrayList<Integer> d = new ArrayList<>();
            d.add(root.val);
            data.add(d);
            return data;
        }
        // 普通节点
        target -= root.val;
        ArrayList<ArrayList<Integer>> l = FindPath(root.left, target);
        ArrayList<ArrayList<Integer>> r = FindPath(root.right, target);
      
        if (l.size() != 0) {
            for (ArrayList<Integer> a : l) {
                a.add(0, root.val);
            }
            data.addAll(l);
        }
        if (r.size() != 0) {
            for (ArrayList<Integer> a : r) {
                a.add(0, root.val);
            }
            data.addAll(r);
        }
        return data;
    }
}