欧美一区二区视频在线77777 ,国产一级a一片成人AV,婷婷五月天在线无码,黄色操逼网站,亚洲婷婷综合网,中国操逼小视频,91十八禁,免费一级色情视频

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?路徑總和 III，我們先來看題面：

https://leetcode-cn.com/problems/path-sum-iii/

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

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

給定一個二叉樹的根節(jié)點 root ，和一個整數(shù) targetSum ，求該二叉樹里節(jié)點值之和等于 targetSum 的路徑的數(shù)目。

路徑不需要從根節(jié)點開始，也不需要在葉子節(jié)點結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點到子節(jié)點）。

示例

解題

https://www.shuzhiduo.com/A/D854DXRp5E/

路徑的開頭可以不是根節(jié)點，結(jié)束也可以不是葉子節(jié)點，是不是有點復(fù)雜？
如果問題是這樣：找出以根節(jié)點為開始，任意節(jié)點可作為結(jié)束，且路徑上的節(jié)點和為 sum 的路徑的個數(shù)；
是不是前序遍歷一遍二叉樹就可以得到所有這樣的路徑？是的；
如果這個問題解決了，那么原問題可以分解成多個這個問題；
是不是和數(shù)線段是同一個問題，只不過線段變成了二叉樹；
在解決了以根節(jié)點開始的所有路徑后，就要找以根節(jié)點的左孩子和右孩子開始的所有路徑，三個節(jié)點構(gòu)成了一個遞歸結(jié)構(gòu)；

/**
?* Definition for a binary tree node.
?* public class TreeNode {
?* int val;
?* TreeNode left;
?* TreeNode right;
?* TreeNode(int x) { val = x; }
?* }
?*/
class?Solution?{
???/**
?????* 求以 root 為根的二叉樹，所有和為 sum 的路徑；
?????* 路徑的開頭不一定是 root，結(jié)尾也不一定是葉子節(jié)點；
?????* @param?root
?????* @param?sum
?????* @return
?????*/
????public?int?pathSum(TreeNode root, int?sum)?{
?
????????if?(root == null) {
????????????return?0;
????????}
?
????????return?paths(root, sum)
????????????????+ pathSum(root.left, sum)
????????????????+ pathSum(root.right, sum);
????}
?
????private?int?paths(TreeNode root, int?sum)?{
?
????????if?(root == null) {
????????????return?0;
????????}
?
????????int?res = 0;
????????if?(root.val == sum) {
????????????res += 1;
????????}
?
????????res += paths(root.left, sum - root.val);
????????res += paths(root.right, sum - root.val);
?
????????return?res;
????}
}