package LeetCode;

public class LeetCode437 {

    /// 437. Path Sum III
    /// https://leetcode.com/problems/path-sum-iii/description/
    /// : O(n), n
    /// : O(h), h


    /// Definition for a binary tree node.
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // root,sum,
      public int pathSum(TreeNode root, int sum) {

        if (root == null)
            return 0;

        return findPath(root, sum)
                + pathSum(root.left, sum)
                + pathSum(root.right, sum);
    }

    // node,node,sum
    // 
    private int findPath(TreeNode node, int num) {

        if (node == null)
            return 0;

        int res = 0;
        // node.val == num 
        if (node.val == num)
            res += 1;

        res += findPath(node.left, num - node.val);
        res += findPath(node.right, num - node.val);

        return res;
    }

    public static void main(String[] args) {

        // Leetcode
        // , , :)

        /*****************
         * :
         *
         *       10
         *      /  \
         *     5   -3
         *    / \    \
         *   3   2   11
         *  / \   \
         * 3  -2   1
         *****************/
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(-2);

        TreeNode node3 = new TreeNode(3);
        node3.left = node1;
        node3.right = node2;

        TreeNode node4 = new TreeNode(1);
        TreeNode node5 = new TreeNode(2);
        node5.right = node4;

        TreeNode node6 = new TreeNode(5);
        node6.left = node3;
        node6.right = node5;

        TreeNode node7 = new TreeNode(11);
        TreeNode node8 = new TreeNode(-3);
        node8.right = node7;

        TreeNode node9 = new TreeNode(10);
        node9.left = node6;
        node9.right = node8;

        System.out.println((new LeetCode437()).pathSum(node9, 8));
    }
}