路经总和
题目描述：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。
示例
:
给定如下二叉树，以及目标和 sum
= 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true
, 因为存在目标和为
22 的根节点到叶子节点的路径
5->4->11->2。
解题思路：采用双栈，一个存结点，一个存当前还需要多少的值，然后同步弹出，同步压入，直至栈空，如果栈空，则没有路径，如果存在弹出的值为0，即为当前路径。
class Solution {
public:
bool hasPathSum(TreeNode
* root
, int sum
) {
if(!root
)return false;
stack
<TreeNode
*>node
;
stack
<int>cur_need
;
int cur_sum
;
TreeNode
* p
;
node
.push(root
);
cur_sum
=sum
-root
->val
;
cur_need
.push(cur_sum
);
while(!node
.empty()){
p
=node
.top();
cur_sum
=cur_need
.top();
node
.pop();
cur_need
.pop();
if(!p
->left
&&!p
->right
&&cur_sum
==0)return true;
if(p
->left
){
node
.push(p
->left
);
cur_need
.push(cur_sum
-p
->left
->val
);
}
if(p
->right
){
node
.push(p
->right
);
cur_need
.push(cur_sum
-p
->right
->val
);
}
}
return false;
}
};
法二：递归 思路：如果当前是叶子节点，则看sum是否满足，如果有左孩子，那么就递归左孩子，如果有右孩子，则递归右孩子，如果左右都有，则返回两个递归，并使用||，即满足一个条件即可
class Solution {
public:
bool hasPathSum(TreeNode
* root
, int sum
) {
if(!root
)return false;
if(!root
->left
&&!root
->right
)return (root
->val
==sum
);
if(!root
->left
)return hasPathSum(root
->right
,sum
-(root
->val
));
if(!root
->right
)return hasPathSum(root
->left
,sum
-(root
->val
));
return hasPathSum(root
->left
,sum
-(root
->val
))||hasPathSum(root
->right
,sum
-(root
->val
));
}
};
