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

DESC:

题目描述

给定一个二叉树和一个值 sum，请找出所有的根节点到叶子节点的节点值之和等于 sum 的路径，

例如：

给出如下的二叉树， sum=22，

返回

[

[5,4,11,2],

[5,8,9]

]

示例1

输入

{1,2},1

返回值

[]

示例2

输入

{1,2},3

返回值

[[1,2]]

CODE:

import java.util.*;/* * public class TreeNode { *   int val = 0; *   TreeNode left = null; *   TreeNode right = null; * } */public class Solution {    /**     *      * @param root TreeNode类      * @param sum int整型      * @return int整型ArrayList
    
     <>>     */    private ArrayList
     
      
       > res = new ArrayList<>();    public ArrayList
       
        
         > pathSum (TreeNode root, int sum) {        // write code here        ArrayList
         
           temp = new ArrayList(); dfs(root, sum, 0, temp); return res; } private void dfs(TreeNode node, int sum, int pathSum, ArrayList
          
            path){ if (node == null) { return; } path.add(node.val); pathSum += node.val; if (node.left == null && node.right == null && sum == pathSum) { res.add(new ArrayList<>(path)); } else { dfs(node.left, sum, pathSum, path); dfs(node.right, sum, pathSum, path); } path.remove(path.size()-1); }}
          
         
        
       
      
     
    

 

DESC:

1. DFS, 回溯
2. 注意每一层执行完，删除当前节点的val，即回溯，便于上层左右节点拼接路径

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