剑指Offer-面试题34-二叉树中和为某一值的路径

2020-05-01

题目描述

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

示例：
给定如下二叉树，以及目标和sum=22

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

[
   [5,4,11,2],
   [5,8,4,5]
]

提示：节点总数<=10000

思路

采用递归，对二叉树进行前序遍历
初始化结果result，路径path
recur(root,tar)函数：
- 参数：当前节点root，当前目标值tar
- 终止条件：当前节点root为空
- 过程
  1. 路径更新：将当前节点值root.val加入路劲path
  2. 目标更新：tar -= root.val（即tar从sum减至0）
  3. 路径记录：当root为叶子结点且tar==0，则将此路径path加入到result中
  4. 路径回溯：回溯前，需要将当前节点的值从路径path中删除，即执行path.removeLast()

代码

/**
 * 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>> result = new LinkedList<>();    //结果
    List<Integer> path = new LinkedList<>();    //路径
    public List<List<Integer>> pathSum(TreeNode root,int sum){
        recur(root,sum);
        return result;
    }
    public void recur(TreeNode root,int tar){
        if(root == null){   //root为空，则直接返回
            return ;
        }
        path.add(root.val); //当前节点加入路径
        tar -= root.val;    //更新目标
        //如果tar==0且当前节点是叶子结点，则将路径加入结果中
        if(tar==0 && root.left==null && root.right==null){
            result.add(new LinkedList(path));
        }
        recur(root.left,tar);   //递归进入左子树
        recur(root.right,tar);  //递归进入右子树
        path.removeLast();  //回溯前将当前节点值从路径中移除（路径恢复）
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。