本文共 2129 字，大约阅读时间需要 7 分钟。

链接：

大意：

给定一棵二叉树根节点root，以及一个整数sum。要求找出所有从根节点到叶子节点路径上数字之和为sum的路径，从上至下输出路径上的值。例子：

思路：

回溯法。

假设遍历到的当前节点记为node，使用subSum记录root到node的和（不包括node的值）。则可有如下几种情况进行分析：

• node == null ： 则直接返回
• node != null && node.left == null && node.right == null：即该节点为 叶子节点，则判断 subSum + node.val == sum是否成立。若成立，则把node.val加入到 l，再将l加入到 res ，之后删除l的最后一个元素（回溯），之后函数立即返回
• 若上述两种情况均不符合，即该节点还并不是叶子节点，则将该节点的值加入到l，subSum += node.val。继续对该节点的左右子树进行同样的操作。最后记得回溯

代码：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public List
   
    
     > pathSum(TreeNode root, int sum) {        List
     
      
       > res = new ArrayList<>();        pathSum(root, 0, sum, res, new LinkedList<>());        return res;    }    public void pathSum(TreeNode root, int subSum, int sum, List
       
        
         > res, LinkedList
         
           l) { if (root == null) return ; // 当前节点是一个叶子节点 if (root.left == null && root.right == null) { if (subSum + root.val == sum) { l.addLast(root.val); res.add(new ArrayList<>(l)); l.removeLast(); } return ; } l.addLast(root.val); pathSum(root.left, subSum + root.val, sum, res, l); pathSum(root.right, subSum + root.val, sum, res, l); l.removeLast(); // 回溯 }}
         
        
       
      
     
    
   

结果：

结论：

 回溯法。应该是可以不需要subSum这个变量的，只需要使用sum依次减去当前节点值即可。

改进：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public List
   
    
     > pathSum(TreeNode root, int sum) {        List
     
      
       > res = new ArrayList<>();        pathSum(root, sum, res, new LinkedList<>());        return res;    }    public void pathSum(TreeNode root, int sum, List
       
        
         > res, LinkedList
         
           l) { if (root == null) return ; // 当前节点是一个叶子节点 if (root.left == null && root.right == null) { if (sum == root.val) { l.addLast(root.val); res.add(new ArrayList<>(l)); l.removeLast(); } return ; } l.addLast(root.val); pathSum(root.left, sum - root.val, res, l); pathSum(root.right, sum - root.val, res, l); l.removeLast(); // 回溯 }}
         
        
       
      
     
    
   

转载地址：http://wxesi.baihongyu.com/