437. Path Sum III

古城微笑少年丶 2021-11-29 18:40 219阅读 0赞

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.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
    
          10
         /  \
        5   -3
       / \    \
      3   2   11
     / \   \
    3  -2   1
    
    Return 3. The paths that sum to 8 are:
    
    1.  5 -> 3
    2.  5 -> 2 -> 1
    3. -3 -> 11

private int _count;
            private int _target;
    
            public int PathSum(TreeNode root, int sum)
            {
                _target = sum;
                Iterate(root);
                return _count;
            }
    
            private void Iterate(TreeNode node)
            {
    
                Chuck(node, 0);
                if (node?.left == null && node?.right == null)
                {
                    return;
                }
                Iterate(node.left);
                Iterate(node.right);
            }
    
            private void Chuck(TreeNode node, int sum)
            {
                if (node == null)
                {
                    return;
                }
    
                sum = sum + node.val;
                if (sum == _target)
                {
                    _count++;
                }
                if (node.left == null && node.right == null)
                {
                    return;
                }
                Chuck(node.left, sum);
                Chuck(node.right, sum);
            }

Runtime: 112 ms, faster than 75.10% of C\# online submissions for Path Sum III.

Memory Usage: 24 MB, less than 56.18% of C\# online submissions for Path Sum III.

转载于:https://www.cnblogs.com/chucklu/p/10925750.html