113. 路径总和 II

 思路:明显可以使用回溯法,和112题很像,先把当前根节点选中,加入temp,之后使用sum1减去根节点数值,然后到了叶子结点,判断sum1是否为零,来判断当前路径是不是符合要求。

遇到符合要求的叶子结点,把当前的路径加入res里面。

假如当前根节点不是叶子结点,递归调用函数处理左右子树

对左右子树的处理,已经成功的把当前root节点下的所有符合要求的路径记录了,之后要回溯,去除此root节点(temp.remove(temp.size()-1);)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<List<Integer>> res=new ArrayList<>();//结果集合
    List<Integer> temp=new ArrayList<>();//存储一个可能的路径的集合
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root==null) return res;
        int sum1=sum;
        sum1-=root.val;//把当前的这个根节点,加入集合temp里面,sum减去这个值。
        temp.add(root.val);//选中当前的根节点
        if(root.left==null&&root.right==null&&sum1==0)//遇到了叶子结点,而且这个路径符合要求,记录下来
        {
            res.add(new ArrayList(temp));
        }
        if(root.left!=null) pathSum(root.left,sum1);//左子树不为空,对左子树调用函数,找左子树下符合要求的路径
        if(root.right!=null) pathSum(root.right,sum1);//右子树不为空,对右子树调用函数,找右子树下符合要求的路径
        temp.remove(temp.size()-1);//对左右子树的处理,已经成功的把当前root节点下的所有符合要求的路径记录了,之后要回溯,去除此root节点
        return res;
    }
}

  

原文地址:https://www.cnblogs.com/lzh1043060917/p/12841722.html