leetcode 113 Solution

代码解析

package com.demo.s113;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 路径总和 II
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *
 * 叶子节点 是指没有子节点的节点。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/path-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
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;
    }
}
public class Solution {
    //定义结果list
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    //定义路径
    Deque<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        //深度遍历
        dfs(root, targetSum);
        return ret;
    }

    public void dfs(TreeNode root, int targetSum) {
        //遍历到叶子节点结束
        if (root == null) {
            return;
        }
        //把遍历路径的值存到队列中
        path.offerLast(root.val);
        //目标值减小
        targetSum -= root.val;
        //直到没有叶子节点了，或者 目标值为0 也就是 路径和 == targetSum了
        if (root.left == null && root.right == null && targetSum == 0) {
            //把队列的路径存到结果list中
            ret.add(new LinkedList<Integer>(path));
        }
        //深度遍历左子树
        dfs(root.left, targetSum);
        //深度遍历右子树
        dfs(root.right, targetSum);
        //把路径中的值弹出
        path.pollLast();
    }
}