6.13 路径总和

112. 路径总和

/**
 * 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 false
        //让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
        return traversal(root,targetSum-root.val);
    }
    /**
     * 
     * @param cur
     * @param count 我们这里先令count == 目标值 每遍历一次减去当前root.val,最后若恰好是叶子节点且count==0 则是终止条件
     * @return
     */
    private boolean traversal(TreeNode cur,int count){
        //终止条件
        if (cur.left == null && cur.right == null){//找到了叶子节点且count==0
            return count == 0;
        }
        //单层递归逻辑
        if (cur.left != null){
            count -= cur.left.val;
            if (traversal(cur.left,count)) return true;//递归   // 遇到叶子节点返回true，则直接返回true
            count += cur.left.val;//回溯 撤销处理结果
        }
        if (cur.right != null){
            count -= cur.right.val;
            if (traversal(cur.right,count)) return true;//递归  // 遇到叶子节点返回true，则直接返回true
            count += cur.right.val;//回溯
        }
        //都不满足返回false
        return false;
    }
}

113. 路径总和 II

public void backtracking(TreeNode node, int targetSum) {
    if (targetSum == 0 && node.left == null && node.right == null) {
       // 注意  这个地方加入的应该是 new ArrayList<>()， 因为对java来说，即使path放入到res 中，之后path进行了改变，res中的path也会变化
        res.add(new ArrayList<>(path));
        return;
    }

    if (node.left != null) {
        path.add(node.left.val);
        targetSum -= node.left.val;
        backtracking(node.left, targetSum);
        targetSum += node.left.val;
        path.remove(path.size() - 1);
    }

    if (node.right != null) {
        path.add(node.right.val);
        targetSum -= node.right.val;
        backtracking(node.right, targetSum);
        targetSum += node.right.val;
        path.remove(path.size() - 1);
    }
    return;
}
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    if (root == null) return res;
    path.add(root.val);
    backtracking(root, targetSum - root.val);
    return res;
}

class solution {
    public list<list<integer>> pathsum(treenode root, int targetsum) {
        list<list<integer>> res = new arraylist<>();
        if (root == null) return res; // 非空判断

        list<integer> path = new linkedlist<>();
        preorderdfs(root, targetsum, res, path);
        return res;
    }

    public void preorderdfs(treenode root, int targetsum, list<list<integer>> res, list<integer> path) {
        path.add(root.val);
        // 遇到了叶子节点
        if (root.left == null && root.right == null) {
            // 找到了和为 targetsum 的路径
            if (targetsum - root.val == 0) {
                res.add(new arraylist<>(path));
            }
            return; // 如果和不为 targetsum，返回
        }

        if (root.left != null) {
            preorderdfs(root.left, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
        if (root.right != null) {
            preorderdfs(root.right, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
    }
}