112. Path Sum

题目描述

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

解题方法

我們透過確認葉子節點是否為sum剩餘的值

也可能為負值，所以不可以判斷pathSum > Sum時就break

ex [2, 1]

non-reursive /recursive way

    public boolean hasPathSum(TreeNode root, int sum){
        if(root == null){ return false;}

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode pre = null;
        int pathSum = 0;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                pathSum += cur.val;          
                cur = cur.left;
            }
            cur = stack.peek();
            if(cur.left == null && cur.right == null && pathSum == sum){
                return true;
            }
            if(cur.right != null && pre != cur.right){
                cur = cur.right;
                continue;
            }
            cur = stack.pop();
            pre = cur;
            pathSum -= cur.val;
            cur = null;
        }
        return false;
    }

    public boolean hasPathSum(Tree
    Node root, int sum){
        /*if(root == null){     //[] 0 : case would be fail
            if(sum == 0){ 
                return true;
            }else{
                return false;
            }
        }*/

        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null && sum - root.val == 0){
            return true;
        }
        boolean bLeft = hasPathSum(root.left, sum - root.val);
        boolean bRight = hasPathSum(root.right, sum - root.val);
        return bLeft || bRight;
    }

113. Path Sum II

题目描述

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:

Given the below binary tree and

sum = 22

解题方法

Search: think about DFS

要掌握Recursive /Non-recursive

public List<List<Integer>> pathSum(TreeNode root, int sum){
        List<List<Integer>> lists = new ArrayList<>();
        if(root == null){return lists;}
        pathSum(root, sum, new ArrayList<Integer>(), lists);
        return lists;
    }

    private void pathSum(TreeNode root, int sum, List<Integer> list, List<List<Integer>> lists){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null && sum - root.val == 0){
            list.add(root.val);
            lists.add(new ArrayList<>(list)); //clone copy
            list.remove(list.size() - 1);
            return;
        }
        list.add(root.val);
        pathSum(root.left, sum - root.val, list, lists);
        pathSum(root.right, sum -root.val, list, lists);
        list.remove(list.size() - 1);
    }

public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int SUM = 0;
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                path.add(cur.val);
                SUM += cur.val;
                cur = cur.left;
            }

            cur = stack.peek();

            if(cur.left == null && cur.right == null && SUM == sum){
                res.add(new ArrayList<Integer>(path));
            }

            if(cur.right != null && cur.right != pre){
                cur = cur.right;
                continue;
            }
            pre = cur;
            stack.pop();
            path.remove(path.size() - 1);
            SUM -= cur.val;
            cur = null;

        }
        return res;
    }

437. Path Sum III

题目描述

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

解题方法

任何起點都可以是頭

    public class Solution {
    /*分析：深度优先搜索，将root以及root->left、root->right结点分别作为开始结点计算下方是否有满足sum的和，dfs函数就是用来计算统计满足条件的个数的。dfs从TreeNode* root开始，查找是否满足sum和的值（此时的sum是部分和），分别dfs左边结点、右边结点，直到找到root->val == sum时候result++，在pathSum函数中返回result的值。*/

    private int res = 0 ;
    public int pathSum(TreeNode root, int sum) {
        if(root == null){
            return 0;
        }
        DFS(root, sum);
        pathSum(root.left, sum);
        pathSum(root.right, sum);
        return res;
    }

    private void DFS(TreeNode root, int sum){
        if(root == null){
            return;
        }
        if(root.val == sum){
            res++;
        }
        DFS(root.left, sum - root.val);
        DFS(root.right, sum - root.val);
    }

}