題目要求：
這個題目說的是畴栖，給你一棵二叉樹和一個整數(shù)分俯，你要判斷這棵二叉樹上是否存在一條從根到葉子節(jié)點的路徑茅特，這條路徑上所有節(jié)點中的數(shù)字相加等于給你的整數(shù)。
比如說爵川，給你的二叉樹是：
1
/
2 4
/
8 16
給你的整數(shù)是 13敷鸦。在這棵二叉樹中存在一條從根到葉子節(jié)點的路徑 1->4->8，路徑上的數(shù)字加起來等于 13，于是要返回 true扒披。
思路：
二叉樹的問題 都可以用遞歸的方式去做值依，遍歷左子樹和右子樹
主要是邊界條件的判斷， 這里要求根到葉子結(jié)點的路徑碟案， 那么最后左右結(jié)點一定為空愿险，
sum之和 可以變成一路子上減掉當(dāng)前結(jié)點的值
遞歸的代碼量只有三行，比較簡單价说，方法如下：
public boolean hasSumRecursive(TreeNode root,int sum){
if(root==null) return false;
if(root.leftnode==null &&root.rightnode==null) return sum==root.val;
return hasSumRecursive(root.leftnode,sum-root.val) ||
hasSumRecursive(root.rightnode,sum-root.val);
}
所以采用第二種方式 迭代的方式一步一步來寫
而二叉樹的迭代方法一般都是用一個棧來存儲數(shù)據(jù)以方便記錄路徑
總結(jié)起來如下：
1辆亏、如果只有根節(jié)點或者找到葉子節(jié)點，我們就把其對應(yīng)的val值返回
2鳖目、如果不是葉子節(jié)點扮叨，我們分別對根節(jié)點的左子樹、右子樹進行遞歸领迈，直到找到葉子結(jié)點彻磁。然后遍歷把葉子結(jié)點和父節(jié)點對應(yīng)的val組成的序列返回上一層；
代碼
import java.util.Stack;
public class PathSum62 {
public class TreeNode{
int val;
TreeNode leftnode;
TreeNode rightnode;
TreeNode(int x){
val=x;
}
}
public boolean hasPathSum(TreeNode root,int sum){
if(root==null){
return false;
}
Stack<TreeNode> stack=new Stack<>();
Stack<Integer> num=new Stack<>();
stack.push(root);
num.push(sum);
while (!stack.isEmpty()){
TreeNode n=stack.pop();
int s=num.pop();
if(n.leftnode==null &&n.rightnode==null&&n.val==s) return true;
if(n.leftnode!=null){
stack.push(n.leftnode);
num.push(s-n.val);
}
if(n.rightnode!=null){
stack.push(n.rightnode);
num.push(s-n.val);
}
}
return false;
}
