剑指 Offer 34. 二叉树中和为某一值的路径-白红宇

剑指 Offer 34. 二叉树中和为某一值的路径

阅读量：4034 次

发布时间：2019-05-24

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

题目描述

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:

给定如下二叉树，以及目标和 target = 22，

5         / \        4   8       /   / \      11  13  4     /  \    / \    7    2  5   1

[

[5,4,11,2],

[5,8,4,5]

]

提示：

节点总数 <= 10000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Java

回溯法

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {
         public List
   
    
     > res;    public List
     
      
       > pathSum(TreeNode root, int target) {
          res= new ArrayList<>();        backtrace(root,target,new ArrayList<>());        return res;    }    public void backtrace(TreeNode root,int target,List
       
         path){
           if(root==null) return;        path.add(root.val);        target-=root.val;        if(target==0 && root.left==null&& root.right==null)            res.add(new ArrayList<>(path));        else{
               backtrace(root.left,target,path);            backtrace(root.right,target,path);        }                path.remove(path.size()-1);    }}