【D4】路径总和 & 路径总和 II (LC 112&113)

112. 路径总和

问题描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。

解题思路

直接递归实现，从根节点开始，用targetSum不断的减去遍历到的每一个节点，一直减到符合条件的叶子节点时，targetSum为0。
注意处理二叉树退化为链表的情况。

代码实现

/**
 * 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 boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return targetSum == 0;
        }

        int newTarget = targetSum - root.val;

        if(root.left == null){
            return hasPathSum(root.right, newTarget);
        }
        if(root.right == null){
            return  hasPathSum(root.left, newTarget);
        }

        return  hasPathSum(root.left, newTarget) || hasPathSum(root.right, newTarget);
    }
}

113. 路径总和 II

问题描述

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。

解题思路

找寻符合叶子条件的思路与上一题基本一致；在采用递归进行先序遍历时将路径节点保存下来即可。
注意：在每次回溯时需要移除最后一个节点

代码实现

/**
 * 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<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        List<Integer> list = new ArrayList<>();
        getResult(root, targetSum, res, list);
        return res;      
    }

    public void getResult(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> list){
        if(root == null){
            return;
        }

        list.add(root.val);
        targetSum = targetSum - root.val;

        if(root.left == null && root.right == null && targetSum == 0){
            //找到符合条件的叶子节点
            res.add(new ArrayList<>(list));
            //此时已将叶子节点添加至路径，进行回溯时需要移除叶子节点
            list.remove(list.size() -1);
            return;
        }
        getResult(root.left, targetSum, res, list);
        getResult(root.right, targetSum, res, list);
        //递归结束时，已将叶子节点添加至路径，进行回溯时需要移除
        list.remove(list.size() -1);
    }
}