Given a binary tree, each node of it holds an integer value.
Find the total number of paths and equals the given value.
The path does not need to start at the root node or end at the leaf node, but the path direction must be downward (only from parent node to child node).
The binary tree has no more than 1000 nodes, and the node value range is an integer of [-1000000,1000000].
Example: root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
The hashmap Ali Tencent byte problem is to solve the path from any node to the descendant node and sum it as a specified value. Note that it doesn't have to start at the root node or end at the leaf node.
A simple way of thinking is to solve it directly recursively, with a spatial complexity o(n) and a time complexity between o(nlogn) and o(n 2), specific**:
/** definition for a binary tree node. *function treenode(val) /// the number of the paths starting from selffunction helper(root, sum) /** param root * param sum * return */var pathsum = function (root, sum) ;subarray-sum-equals-kIf you can solve the problem o(n), the problem will not be very difficult, but the array will be replaced with a binary tree.
There's a difference here, and I'll explain why there's onehashmap[acc] = hashmap[acc] -1;The reason is very simple, that is, when we dfs, when we go back from the bottom to the top, the value of the map should also be backtracked. If you're familiar with the retrospective method, it should be easy to understand, and this question is passedtemplist.pop()to finish.
In addition, I drew a diagram, I believe you will understand after reading it.
When we get to the bottom:
And then go back up:
It's easy to see that our hashmap shouldn't have the same record as the first one, so it needs to be subtracted.
See the ** area below for specific implementation.
Through hashmap, space-for-time language support: js, pythonjs code:
lc app=leetcode id=437 lang=j**ascript * 437] path sum iii *//** definition for a binary tree node. *function treenode(val) /function helper(root, acc, target, hashmap) if (hashmap[acc] === void 0) else const res = count + helper(root.left, acc, target, hashmap) +helper(root.right, acc, target, hashmap);Note here that you don't forget hashmap[acc] = hashmap[acc] -1; return res;}var pathsum = function (root, sum) ;return helper(root, 0, sum, hashmap);}python code:
import collections'''class treenode: def __init__(self, val=0, left=none, right=none): self.val = val self.left = left self.right = right'''class solution: def helper(self,root,acc,target,hashmap): if not root: return 0 count=0 acc+=root.val if acc==target: count+=1 if acc-target in hashmap: count+=hashmap[acc-target] hashmap[acc]+=1 if root.left: count+=self.helper(root.left,acc,target,hashmap) if root.right: count+=self.helper(root.right,acc,target,hashmap) hashmap[acc]-=1 return count def pathsum(self, root: optional[treenode], targetsum: int) -int: hashmap=collections.defaultdict(lambda:0) return self.helper(root,0,targetsum,hashmap)