编程题—剑指offer: 二叉树中和为某一值的路径-白红宇

编程题—剑指offer: 二叉树中和为某一值的路径

阅读量：2442 次

发布时间：2019-05-10

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

题目描述

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例:给定如下二叉树，以及目标和 sum = 22，              5             / \            4   8           /   / \          11  13  4         /  \    / \        7    2  5   1返回:[   [5,4,11,2],   [5,8,4,5]]来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

1、深度优先搜索，存在一个List里面，如果和为指定的数字则存入即可坑点：1、必须是根到叶子节点才算是满足条件的路径2、数字有可能是负数、不要加到比给定的数字大就停止

通过代码

class Solution {
       LinkedList
   
     flag = new LinkedList
    
     ();    List
     
      
       > res = new ArrayList
       
        
         >(); public List
         
          
           > pathSum(TreeNode root, int sum) { find(root, sum, 0); return res; } public void find(TreeNode root,int sum,int num){ if (root==null) return ; else if ((num+root.val==sum)&&(root.left==null)&&(root.right==null)){ flag.add(root); List
           
             res1= new ArrayList
            
             (); for(int i=0;i